|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2007/courses/uspenski.html
Дата изменения: Thu Jun 21 21:30:38 2007 Дата индексирования: Sat Dec 22 16:38:38 2007 Кодировка: koi8-r Поисковые слова: trees |
В.А.Успенский планирует провести две лекции.
Теорема Гёделя о неполноте — едва ли не самая знаменитая теорема математики. Она утверждает, что какие бы способы доказывания ни предложить, в любом достаточно богатом языке найдутся истинные, но не доказуемые утверждения. Богатство языка есть его способность выражать факты. Оказывается, что для целей теоремы Гёделя богатство языка достаточно понимать как его способность выражать принадлежность натуральных чисел перечислимым множествам.
Понятие перечислимого множества — одно из основных понятий теории алгоритмов: непустое множество называется перечислимым, если его можно расположить в вычислимую последовательность. Таким образом, теорема Гёделя имеет алгоритмические истоки. Возможны четыре принципиально различные пути, ведущие от этих истоков к теореме; эти пути были предложены, сооответственно, Гёделем, Колмогоровым, Чейтином и Шенем.
Предполагается в течение двух лекций изложить указанные пути.
Предварительных знаний не требуется. Необходимые факты из теории алгоритмов будут без доказательств сообщаться по ходу изложения.
