Очевидно, что для заданной четверки чисел ( x, у, z, ω ) выяснить, выполняется это равенство или нет, можно простым вычислением. Значит, мы можем представить себе вычислительный алгоритм, который последовательно перебирает все возможные четверки чисел одну за другой и останавливается только тогда, когда равенство удовлетворяется. (Мы уже знаем, что для конечных наборов чисел существуют способы их кодирования на ленте вычислимым способом, а именно, в виде одного числа. Таким образом, перебор всех четверок можно провести, просто следуя естественному порядку соответствующих им одиночных чисел.) Если бы мы могли установить, что этот алгоритм никогда не останавливается, то это стало бы доказательством утверждения Ферма.
Сходным образом в терминах проблемы остановки машины Тьюринга можно перефразировать многие другие нерешенные математические проблемы. Примером такого рода проблем может служить так называемое предположение Гольдбаха: любое четное число, большее двух, может быть представлено в виде суммы двух простых чисел [52]). Процесс, с помощью которого можно установить, относится некоторое натуральное число к простым или нет, является алгоритмическим, поскольку достаточно проверить делимость данного числа на все числа, меньшие его, а это достигается с помощью конечного числа вычислительных операций. Мы можем придумать машину Тьюринга, которая перебирает четные числа 6, 8, 10, 12, 14…, пробуя все возможные способы разбиения их на пары нечетных чисел
6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 +5,
12 = 5 + 7, 14 = 3 + 11=7 + 7…
и убеждаясь, что для каждого четного числа какое-то из разбиений образовано двумя простыми числами. (Очевидно, нам не надо проверять пары четных слагаемых, кроме 2 + 2, поскольку все простые числа за исключением 2 — нечетные.) Наша машина должна остановиться только в том случае, если она находит четное число, для которого ни одно из разбиений не является парой простых чисел. В этом случае мы получили бы контрпример к предположению Гольдбаха, т. е. нашли бы четное число, большее 2, которое не является суммой двух простых чисел. Следовательно, если бы мы могли установить, останавливается машина Тьюринга когда-нибудь или нет, то тем самым мы выяснили бы, справедливо предположение Гольдбаха или нет.
Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга (в которую введены конкретные начальные данные) или нет? Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи. Так существует ли некая алгоритмическая процедура для решения общей проблемы — проблемы остановки — полностью механическим путем? Тьюринг показал, что такой процедуры на самом деле нет.
В сущности, его доказательство сводилось к следующему. Предположим, наоборот, что указанный алгоритм существует [53]. Тогда существует и некая машина Тьюринга Н, которая «решает», остановится ли в конце концов n -я машина Тьюринга, действуя на число m . Условимся, что результатом действия машины Н будет лента с номером 0, если n -я машина не останавливается, и с номером 1 в противоположном случае:
Здесь мы могли бы воспользоваться способом кодирования пары ( n , m ), использованным ранее для универсальной машины Тьюринга U. Однако это привело бы к проблеме технического характера, поскольку при некоторых n (например, n = 7) T n будет определена некорректно, и маркер 111101 будет непригоден для отделения на ленте n от m . Чтобы избежать этой проблемы, будем полагать, что n представлено не в двоичной, а в расширенной двоичной форме, тогда как для m будет по-прежнему использоваться обычная двоичная запись. В этом случае комбинации 110 будет достаточно для разделения n и m . Использование точки с запятой в обозначении Н( n ; m ) в отличие от запятой в обозначении универсальной машины U( n , m ) указывает на это различие в кодировании.
52
Напомним, что простые числа 2, 3, 5, 7, 11, 13, 17… - это такие натуральные числа, которые делятся только на самих себя и на единицу. Ни нуль, ни единица простыми числами не считаются.
53
Это хорошо известный и очень мощный метод математического доказательства, называемый «доказательством от противного» или