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

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

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

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