Десять великих идей науки. Как устроен наш мир.

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t₂₃, и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (h здесь от английского глагола «halt» — останавливаться). Если th получает остановку для частной комбинации программы и данных, например t₂₃ и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t₂₂ и 17, th напечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что th не включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата.

Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t₀, t₁, t₂, … и составляем таблицу, верхним левым фрагментом которой является следующая:

Вход		0	1	2	3
Номер матрицы	0	□	□	□	□
	1	3	□	4	1
	2	1	1	1	1
	3	0	1	□	2

Когда вычисления не останавливаются, мы записываем символ □. Таблица содержит все возможные вычислимые числа (числа, которые могут быть вычислены машиной Тьюринга до произвольного числа разрядов), поскольку она содержит в своих последовательных рядах все возможные машины Тьюринга, а в последовательных колонках все возможные входы.

Теперь мы делаем второй шаг. На этот раз мы рассортируем результаты с помощью машины th, которая настроена так, что выдает 0, если решает, что соответствующие вычисления не остановятся, и не выдает никаких данных, если решает, что вычисления остановятся. Она также делает себе пометку, чтобы запомнить, где она заменила □ на 0, так как не хочет, чтобы машина, программа которой имитируется, была снова втянута в бесконечные вычисления. Например, когда мы загружаем в машину th число 4, а затем число 2, она, в соответствии с программой t₄ и данными 2, инспектирует ленту, производит некоторого рода вычисления, решает, что вычисление t₄(2) не остановится, если мы будем его выполнять, и поэтому ставит 0 в соответствующую ячейку таблицы и делает себе пометку, что данное вычисление не остановится. В конце этого этапа вычислений верхний левый фрагмент таблицы выглядит так:

Вход		0	1	2	3
Номер матрицы	0	0	0	0	0
	1		0
	2
	3			0

Теперь там, где мы не обнаруживаем 0, мы производим все вычисления, как мы это делали на первом шаге, и получаем следующий фрагмент таблицы:

Вход		0	1	2	3
Номер матрицы	0	0	0	0	0
	1	3	0	4	1
	2	1	1	1	1
	3	0	1	0	2

Поскольку исходная таблица содержит все возможные вычислимые числа, эта таблица тоже содержит все возможные вычислимые числа: здесь может быть много повторений, но это делу не мешает.

Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на th и машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th, которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblem не имеет решения.