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

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





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






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


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

Л. Д. Беклемишев
Видеозаписи:
Flash Video 536.4 Mb
Flash Video 3,214.2 Mb
MP4 536.4 Mb
Материалы:
Рисунок 7.1 Kb

Количество просмотров:
Эта страница:255
Видеофайлы:150
Материалы:37

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


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

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

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

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


Материалы: 5217.jpg (7.1 Kb)
Цикл лекций

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