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

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






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


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

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

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

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



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

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

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


Website: https://www.mccme.ru/dubna/2016/courses/sossinsky.html
Цикл лекций
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024