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

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например 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не имеет решения.