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

Предлагаемый курс имеет три основные цели:

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

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