Новый ум короля: О компьютерах, мышлении и законах физики

(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х, у, z, , для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогдане выполняется [49] [50]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство [51], ни найти опровергающий это утверждение пример!

Очевидно, что для заданнойчетверки чисел ( 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в противоположном случае: