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