Лев Дмитриевич Беклемишев

Быстрорастущие функции («быстрее, выше, сильнее»).

Л.Д.Беклемишев планирует провести 4 занятия

Речь пойдет о некоторых совершенно элементарных по формулировке комбинаторных задачах, которые приводят к вычислимым функциям, имеющим невообразимо большой рост. О роли такого рода функций в математической логике будет упомянуто, но основное содержание — знакомство слушателей с примерами и сопутствующими понятиями.

Примерный план:

1. 1. Примитивно рекурсивные функции и функция Аккермана.
2. 2. «Долгие игры»: Геракл-Гидра, последовательность Гудстейна.
3. 3. Теорема Крускала о вложениях деревьев и функция Фридмана.
4. 4. Busy beaver: функция, превосходящая по росту любую вычислимую.
   (В пункте 4 полезно предварительное знакомство слушателей с машинами Тьюринга.)

Organization Committee e-mail:
dubna@mccme.ru