Семинар на секция “Изследване на операциите, вероятности и статистика”
Семинар на секция “Изследване на операциите, вероятности и статистика”
На 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/. Ще разкажа за моето участие в решаването на задачата и за […]