Карта → событие
Тьюринг: что такое «вычислить»
Вопрос, оставшийся от ГильбертаДавид ГильбертЧеловек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти.
В 1928 году Гильберт и Аккерман сформулировали последнюю из своих задач об основаниях — Entscheidungsproblem, проблему разрешения: существует ли механическая процедура, которая по любой формуле логики первого порядка за конечное время отвечает, общезначима она или нет?
Через три года Гёдель в Кёнигсберге обрушил соседние ожидания программы Гильберта — полноту и доказуемость непротиворечивости. Но проблема разрешения устояла: она не про то, что доказуемо, а про то, что вычислимо.
Здесь есть асимметрия, из-за которой задача и оказалась трудной.
Чтобы ответить «да», достаточно предъявить процедуру: вот она, работает. Чтобы ответить «нет», надо высказаться обо всех мыслимых процедурах сразу — а для этого нужно знать, что такое процедура вообще. Двадцать три века математики прекрасно пользовались алгоритмами, ни разу не определив это слово.
Определение через человека
Ход Алана Тьюринга, двадцатичетырёхлетнего выпускника Кингс-колледжа, состоял не в том, чтобы придумать список разрешённых операций. Он стал разбирать, что делает человек, когда считает.
В 1936 году слово computer означало именно человека — вычислителя, сидящего с карандашом и бумагой (такие конторы описаны в этой же линии на примере парижской мастерской Прони). Тьюринг заметил про него четыре вещи:
- он пользуется конечным набором различимых знаков — иначе он их перепутает;
- в каждый момент он смотрит на ограниченный кусок бумаги;
- его «состояние ума» тоже принимает конечное число значений — иначе сколь угодно близкие состояния были бы неразличимы;
- следующее действие зависит только от того, что он видит, и от состояния.
Отсюда механически получается устройство: бесконечная лента, разбитая на клетки, головка, видящая одну клетку, конечное множество состояний и таблица переходов «состояние + символ → новый символ, сдвиг, новое состояние». Всё.
Вот полная машина, определяющая чётность числа палочек на ленте:
| Состояние | Видит | Пишет | Сдвиг | Новое состояние |
|---|---|---|---|---|
| $q_0$ | палочку | палочку | вправо | $q_1$ |
| $q_1$ | палочку | палочку | вправо | $q_0$ |
| $q_0$ | пусто | «чётно» | стоп | — |
| $q_1$ | пусто | «нечётно» | стоп | — |
Четыре строки. Важно, что это не модель человека-вычислителя в смысле упрощения, а разбор: Тьюринг доказывает, что ничего, кроме перечисленного, вычислитель делать и не может.
Диагональ
Дальше идёт рассуждение, которое стоит помнить целиком, — оно занимает пять строк.
Предположим, что существует программа $\mathrm{Ост}(p,x)$, которая по тексту программы $p$ и входу $x$ всегда за конечное время отвечает, остановится ли $p$ на $x$.
Построим программу $D$, которая получает на вход текст программы $p$ и делает так:
- если $\mathrm{Ост}(p,p)$ отвечает «остановится» — уходит в вечный цикл;
- если отвечает «не остановится» — немедленно останавливается.
Спросим: что делает $D$, если подать ей на вход её собственный текст?
- Если $D$ на входе $D$ останавливается, то $\mathrm{Ост}(D,D)$ ответил «остановится», и по построению $D$ ушла в вечный цикл. Противоречие.
- Если $D$ на входе $D$ не останавливается, то $\mathrm{Ост}(D,D)$ ответил «не остановится», и по построению $D$ остановилась. Противоречие.
Значит, программы $\mathrm{Ост}$ не существует. $\blacksquare$
Это тот же приём, которым Кантор доказал несчётность отрезка, а РасселБертран РасселТремя строчками разрушил дело чужой жизни, десять лет чинил сломанное, а потом ушёл из математики в философию и политику — и получил Нобелевскую премию по литературе. выбил фундамент из-под Фреге: объект, определённый через самого себя с отрицанием.
Честная оговорка: у самого Тьюринга теорема сформулирована иначе — о машинах, печатающих бесконечную последовательность знаков («circle-free»), и неразрешимо там свойство быть такой машиной. Привычная формулировка про остановку и само название «проблема остановки» появились позже, у Мартина Дэвиса в 1958 году. Суть от переформулировки не изменилась.
Универсальная машина
И тут же, между делом, в той же статье — самое важное для будущего.
Раз машина задаётся конечной таблицей, её можно записать на ленту как данные. Тьюринг строит машину $U$, которая читает описание любой машины $M$ вместе с входом $x$ и делает ровно то, что сделала бы $M$:
$$U(\langle M\rangle,\ x) = M(x).$$
Это универсальная машина, и это чертёж компьютера: одно устройство, которое исполняет любую программу, потому что программа для него — такие же данные, как всё остальное. До первой машины с хранимой программой оставалось двенадцать лет, а до МЭСМ — пятнадцать. Фон Нейман статью Тьюринга знал.
Ответ Гильберту
Дальше остаётся техника. Работу машины можно записать формулой логики первого порядка так, что формула общезначима тогда и только тогда, когда машина останавливается. Значит, умей мы решать проблему разрешения — умели бы решать и проблему остановки. А её решать нельзя.
Entscheidungsproblem неразрешима. Последний пункт программы Гильберта закрыт, и закрыт отрицательно.
Тезис Чёрча — Тьюринга
В том же 1936 году то же самое сделали ещё дважды: Алонзо ЧёрчАлонзо ЧёрчОтветил Гильберту «нет» за семь месяцев до Тьюринга — и сделал это на языке, где нет ни чисел, ни машин, а есть только функции и подстановка; из этого языка выросло функциональное программирование. в Принстоне через $\lambda$-исчисление, а ГёдельКурт ГёдельДоказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет. и Клини — через общерекурсивные функции. Три определения, построенные из совершенно разного материала, задали один и тот же класс функций.
Отсюда тезис Чёрча — Тьюринга: вычислимое в интуитивном смысле — это в точности вычислимое машиной Тьюринга. Это не теорема и теоремой быть не может: он приравнивает точное понятие к неточному. Но за девяносто лет ни одна новая модель вычислений — нормальные алгорифмы МарковаАндрей Андреевич МарковПридумал цепи зависимых событий, чтобы выиграть спор о том, обязательна ли независимость для закона больших чисел, — и проверил их на буквах «Евгения Онегина»., машины Поста, регистровые машины, любой язык программирования, квантовый компьютер — не вышла за этот класс. Квантовый компьютер меняет скорость, а не круг вычислимого.
Гёдель, обычно скупой на похвалы, писал, что только анализ Тьюринга сделал понятие вычислимости абсолютным: своё собственное определение через рекурсивные функции он считал условным, а тьюринговское — окончательным.
Что было дальше
Война. С 1939 года — Блетчли-парк и «Энигма». Там Тьюринг сделал ещё одну вещь, которую пришлось переоткрывать заново: байесовский вывод с накоплением веса свидетельства.
1950. Статья «Computing Machinery and Intelligence» в журнале Mind: вопрос «может ли машина мыслить» заменён на игру в имитацию — тест Тьюринга.
1952. «The Chemical Basis of Morphogenesis»: система реакция — диффузия, из которой сами собой возникают пятна и полосы. Человек, определивший, что такое вычисление, основал заодно математическую биологию.
1952, второе. Обвинение в «грубой непристойности» — Тьюринг заявил в полицию о краже и в ходе следствия рассказал о своих отношениях с мужчиной. Приговор: принудительная гормональная терапия, потеря допуска к секретным работам.
7 июня 1954 года он умер, сорока одного года, от отравления цианидом. Вердикт коронера — самоубийство; мать до конца считала, что это несчастный случай в домашней лаборатории.
Извинение британского правительства принесено в 2009 году, королевское помилование подписано в 2013-м, закон об аннулировании подобных приговоров («закон Тьюринга») принят в 2017-м. Главная премия по информатике носит его имя с 1966 года.
Задача. Докажите, что не существует программы, которая по тексту любой программы определяет, напечатает ли та когда-нибудь цифру 7.
(Ответ: пусть такая программа $S$ есть. По паре $(p,x)$ построим программу $R$, которая молча моделирует работу $p$ на входе $x$ и, если та остановилась, печатает 7 — и больше нигде семёрок не печатает. Тогда $S(R)$ отвечает ровно на вопрос, останавливается ли $p$ на $x$. Проблема остановки оказалась бы разрешима, а она неразрешима.)
Соседние точки. В линии логики: Чёрч (апрель 1936) → Тьюринг → Генцен и Мальцев (тот же 1936-й), а дальше Новиков (1955) и Матиясевич (1970) разносят неразрешимость по математике. В дискретной: Кёниг (1931) → Тьюринг → Канторович (1939). Отсюда же тянутся нити к Блетчли-парку и к Шеннону.