Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2012/courses/ldb.htm
Дата изменения: Thu May 31 10:55:48 2012
Дата индексирования: Mon Feb 4 06:49:22 2013
Кодировка: koi8-r
Поисковые слова: http astrokuban.info astrokuban
Dubna-2012: Beklemishev
На главную страницу ЛШСМ-2012 К списку курсов ЛШСМ-2012

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

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

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

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

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

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