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

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





Для просмотра файлов Вам могут потребоваться






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


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

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

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

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


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

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

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

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

Цикл лекций

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