Лев Дмитриевич Беклемишев
Быстрорастущие функции («быстрее, выше, сильнее»).
Л.Д.Беклемишев планирует провести 4 занятия
Речь пойдет о некоторых совершенно элементарных по формулировке комбинаторных задачах, которые приводят к вычислимым функциям, имеющим невообразимо большой рост. О роли такого рода функций в математической логике будет упомянуто, но основное содержание — знакомство слушателей с примерами и сопутствующими понятиями.
Примерный план:
- 1. Примитивно рекурсивные функции и функция Аккермана.
- 2. «Долгие игры»: Геракл-Гидра, последовательность Гудстейна.
- 3. Теорема Крускала о вложениях деревьев и функция Фридмана.
- 4. Busy beaver: функция, превосходящая по росту любую вычислимую.
(В пункте 4 полезно предварительное знакомство слушателей с машинами Тьюринга.)
Organization Committee e-mail:
dubna@mccme.ru