Алексей Брониславович Сосинский

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

А. Б. Сосинский планирует провести 4 занятия.

Доступны 4 видеозаписи курса.

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

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

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

Программа курса

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

Organization Committee e-mail:
dubna@mccme.ru