Аннотация:
Предлагаемый курс имеет три основные цели:
доказать, что возможности компьютера принципиально ограничены («существование алгоритмически неразрешимых проблем»);
объяснить, чем сложные и случайные последовательности отличаются от простых («сложность Колмогорова»);
показать, что в математике существуют утверждения, которые нельзя ни доказать, ни опровергнуть («первая теорема Гёделя о неполноте»).
В курсе не будут использоваться никакие знания, выходящие за пределы школьной программы (так что курс формально доступен школьникам), но это не значит, что это – простой курс: потребуются хорошие мозги и большое напряжение ума, чтобы понять те глубокие (и печальные!) факты, которые в нем будут рассказаны.
Программа курса
Машина Тюринга, тезис Черча, вычислимые функции, перечислимые и разрешимые множества.
Универсальная машина Тюринга, существование перечислимых, но неразрешимых множеств, неразрешимые проблемы теории алгоритмов, задачи, принципиально не доступные компьютеру.
Сложность двоичных последовательностей по Колмогорову.
Формальная математика, теорема Гёделя и – если хватит времени – ее доказательство по Чейтину.
Обратная связь: