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

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

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