Неразрешимость проблемы Гильберта
Мы теперь вплотную подходим к той цели, ради которой Тьюринг с самого начала разрабатывал свою теорию — получить ответ на вопрос, заключенный в общей проблеме алгоритмической разрешимости, поставленной Гильбертом, а именно: существует ли некая механическая процедура для решения всех математических задач, принадлежащих к некоторому широкому, но вполне определенному классу? Тьюринг обнаружил, что он мог бы перефразировать этот вопрос следующим образом: остановится ли в действительности n- я машина Тьюринга, если на ее вход поступит число m Эта задача получила название проблемы остановки . Не так сложно составить список команд, для которых машина никогда не остановится при любом m (как, например, в случаях n = 1 или 2, рассмотренных в предыдущем разделе, а также во всех случаях, когда вообще отсутствует команда STOP). Точно так же существует множество списков команд, для которых машина будет останавливаться всегда, независимо от вводимого числа m (например, T 11 ). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими — нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины T n над данным числом m к какому-то ответу или нет! Если нет (т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:
T n (m ) = □.
(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин T 4 и T 1 . К сожалению, наша на первый взгляд работоспособная машина T 3 должна теперь также считаться фиктивной, т. е.
T 3 (m ) = □, поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T 11 , однако, совершенно полноправна, поскольку она производит единственную 1. Результатом ее работы будет лента с номером 0, так что T 11 ( m ) = 0 для любого m .)
В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение
( х+ 1) ω+3+ ( у+ 1) ω+3= ( z+ 1) ω+3.
(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х , у , z , ω , для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогда не выполняется [49] [50]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство [51], ни найти опровергающий это утверждение пример!
49
Напомним, что
50
Желающие ознакомиться с вопросами, имеющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратиться к работе Дэвлина [1988].
51
Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. —