Семинар на секция ИОВС
Боян Стефанов
Следващото заседание на семинара на секция ИОВС ще се състои на
14-ти май, сряда, от 15:00 ч. в зала 503 на ИМИ.
Лектор ще бъде д-р Георги Георгиев от ФМИ на СУ, темата на лекцията е:
„Busy Beaver за n=5, или колко сложни са простите програми“
Резюме:
Колко дълго може да работи машина на Тюринг с 5 състояния и азбука {0,1}, преди да спре?
В началото лентата е запълнена с нули.
Известна под името „Busy Beaver за n=5“ или BB(5), задачата е разбираема за всеки ученик, който се интересува от програмиране.
Решаването ѝ продължи 40 години и демонстрира колко сложен е семантичният анализ дори на микроскопични програми.
Историята бе разказана увлекателно преди година в списанието Quanta Magazine:
Ще разкажа за моето участие в решаването на задачата и за връзката ѝ с фундаменталните ограничения на методите за математическо и научно изследване.