Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика», 2012
22 июля 2012 г. 17:00, г. Дубна
 


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

Л. Д. Беклемишев
Видеозаписи:
Flash Video 3,066.4 Mb
Flash Video 511.7 Mb
MP4 511.7 Mb

Количество просмотров:
Эта страница:633
Видеофайлы:280

Л. Д. Беклемишев


Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке

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

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

Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021