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

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





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






Летняя школа «Современная математика», 2016
26 июля 2016 г. 09:30, г. Дубна, дом отдыха «Ратмино»
 


Теория алгоритмов: от машины Тюринга до теоремы Гёделя. Занятие 2

А. Б. Сосинский
Видеозаписи:
Flash Video 2,936.2 Mb
Flash Video 490.0 Mb

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

А. Б. Сосинский


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

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

Аннотация: Предлагаемый курс имеет три основные цели:
  • доказать, что возможности компьютера принципиально ограничены («существование алгоритмически неразрешимых проблем»);
  • объяснить, чем сложные и случайные последовательности отличаются от простых («сложность Колмогорова»);
  • показать, что в математике существуют утверждения, которые нельзя ни доказать, ни опровергнуть («первая теорема Гёделя о неполноте»).

В курсе не будут использоваться никакие знания, выходящие за пределы школьной программы (так что курс формально доступен школьникам), но это не значит, что это – простой курс: потребуются хорошие мозги и большое напряжение ума, чтобы понять те глубокие (и печальные!) факты, которые в нем будут рассказаны.

Программа курса
  • Машина Тюринга, тезис Черча, вычислимые функции, перечислимые и разрешимые множества.
  • Универсальная машина Тюринга, существование перечислимых, но неразрешимых множеств, неразрешимые проблемы теории алгоритмов, задачи, принципиально не доступные компьютеру.
  • Сложность двоичных последовательностей по Колмогорову.
  • Формальная математика, теорема Гёделя и – если хватит времени – ее доказательство по Чейтину.


Website: http://www.mccme.ru/dubna/2016/courses/sossinsky.html
Цикл лекций

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