Лекторий Малого мехмата МГУ: Малыхин Юрий Вячеславович, «Очень долго работающие машины Тьюринга».

Лекция сотрудника лаборатории «Многомерная аппроксимация и приложения» механико-математического факультета МГУ Малыхина Юрия Вячеславовича «Очень долго работающие машины Тьюринга». В докладе речь пойдёт о фундаментальном объекте Computer Science — функции BusyBeaver(N) (далее: BB), равной максимальному количеству шагов, которые может сделать машина Тьюринга с N состояниями (вариант: компьютерная программа из N символов) перед остановкой. Поводом к докладу послужило то, что летом 2024 г. нашли (доказали, чему равно) значение BB(5). В функции BB отражается вся сложность, заложенная в понятии вычислимости; будут рассмотрены также некоторые математические проблемы, связанные с этой функцией.