|
Теперь мы делаем второй шаг. На этот раз мы рассортируем результаты с помощью машины th , которая настроена так, что выдает 0, если решает, что соответствующие вычисления не остановятся, и не выдает никаких данных, если решает, что вычисления остановятся. Она также делает себе пометку, чтобы запомнить, где она заменила ? на 0, так как не хочет, чтобы машина, программа которой имитируется, была снова втянута в бесконечные вычисления. Например, когда мы загружаем в машину th число 4, а затем число 2, она, в соответствии с программой t4 и данными 2, инспектирует ленту, производит некоторого рода вычисления, решает, что вычисление t4(2) не остановится, если мы будем его выполнять, и поэтому ставит 0 в соответствующую ячейку таблицы и делает себе пометку, что данное вычисление не остановится. В конце этого этапа вычислений верхний левый фрагмент таблицы выглядит так: Вход0123Номер матрицы 0 00001 0 2 3 0 Теперь там, где мы не обнаруживаем 0 , мы производим все вычисления, как мы это делали на первом шаге, и получаем следующий фрагмент таблицы: Вход0123Номер матрицы 0 0 0001 30 412 111 13 0102 Поскольку исходная таблица содержит все возможные вычислимые числа, эта таблица тоже содержит все возможные вычислимые числа: здесь может быть много повторений, но это делу не мешает. Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на th и машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th , которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblem не имеет решения. — 281 —
|