На 14 май (сряда) от 15:00 ч. в зала 503 на ИМИ
ще се състои сбирка на Семинара на секция ИОВС.  Доклад на тема:

Busy Beaver за n=5, или колко сложни са простите програми

ще изнесе д-р Георги Георгиев от ФМИ на СУ.

Резюме. Колко дълго може да работи машина на Тюринг с 5 състояния и азбука {0,1}, преди да спре?
В началото лентата е запълнена с нули.
Известна под името „Busy Beaver за n=5“ или BB(5), задачата е разбираема за всеки ученик, който се интересува от програмиране.
Решаването ѝ продължи 40 години и демонстрира колко сложен е семантичният анализ дори на микроскопични програми.

Историята бе разказана увлекателно преди година в списанието Quanta Magazine:
https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/.

Ще разкажа за моето участие в решаването на задачата и за връзката ѝ с фундаменталните ограничения на методите за математическо и научно изследване.