275817487333272966
789987984732840981
907648512726310017
401667873634776058
572450369644348979
920344899974556624
029374876688397514
044516657077500605
138839916688140725
455446652220507242
623923792115253181
625125363050931728
631422004064571305
275802307665183351
995689139748137504
926429605010013651
980186945639498
(или какому-нибудь другому подходящему, не менее внушительному по величине числу). Это число, без сомнения, выглядит устрашающе большим! Оно, действительно, чрезвычайно велико, но я не вижу способа, как его можно было бы сделать меньше. Процедуры кодирования и определения, использованные мною для машин Тьюринга, вполне разумны и достаточно просты, и все же с неизбежностью приводят к подобным несуразно большим числам для реальной универсальной машины Тьюринга[48].
Я уже говорил, что все современные общеупотребительные компьютеры, по сути, являются универсальными машинами Тьюринга. Я ни в коем случае не подразумеваю под этим, что их логическая структура должна в точности походить на предложенную мной выше структуру универсальной машины Тьюринга. Однако суть дела состоит в том, что если сперва ввести в произвольную универсальную машину Тьюринга соответствующую программу (начало подаваемой на вход ленты), то потом она сможет копировать поведение любой машины Тьюринга! В предыдущем примере программа просто принимает форму одного числа (числа n ), но этим разнообразие возможных процедур и вариантов исходной схемы Тьюринга отнюдь не исчерпывается. В действительности я сам, описывая машину, несколько отклонился от того, что исходно было предложено Тьюрингом. Но ни одно из этих отклонений не имеет сейчас для нас существенного значения.
Неразрешимость проблемы Гильберта
Мы теперь вплотную подходим к той цели, ради которой Тьюринг с самого начала разрабатывал свою теорию — получить ответ на вопрос, заключенный в общей проблеме алгоритмической разрешимости, поставленной Гильбертом, а именно: существует ли некая механическая процедура для решения всех математических задач, принадлежащих к некоторому широкому, но вполне определенному классу? Тьюринг обнаружил, что он мог бы перефразировать этот вопрос следующим образом: остановится ли в действительности n-я машина Тьюринга, если на ее вход поступит число m Эта задача получила название проблемы остановки. Не так сложно составить список команд, для которых машина никогда не остановится при любом m (как, например, в случаях n = 1 или 2, рассмотренных в предыдущем разделе, а также во всех случаях, когда вообще отсутствует команда STOP ). Точно так же существует множество списков команд, для которых машина будет останавливаться всегда, независимо от вводимого числа m (например, T11 ). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими — нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины Tn над данным числом m к какому-то ответу или нет! Если нет (т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:
Tn(m ) = □.
(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин T4 и T1. К сожалению, наша на первый взгляд работоспособная машина T3 должна теперь также считаться фиктивной, т. е.
T3(m ) = □, поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T11, однако, совершенно полноправна, поскольку она производит единственную 1. Результатом ее работы будет лента с номером 0, так что T11(m ) = 0 для любого m.)
В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение
(х + 1)ω+3 + (у + 1)ω+3 = (z + 1)ω+3.
(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х, у, 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, которое не является суммой двух простых чисел. Следовательно, если бы мы могли установить, останавливается машина Тьюринга когда-нибудь или нет, то тем самым мы выяснили бы, справедливо предположение Гольдбаха или нет.
48
Я благодарен Давиду Дойчу за то, что он нашел десятичную форму двоичного представления u, которое я привожу ниже. Я признателен ему также за проверку того факта, что это двоичное значение и действительно задает универсальную машину Тьюринга! Двоичная запись и выглядит следующим образом:
10000000010111010011010
00100101010110100011010
00101000001101010011010
00101010010110100001101
00010100101011010010011
10100101001001011101010
00111010101001001010111
01010100110100010100010
10110100000110100100000
10101101000100111010010
10000101011101001000111
01001010100001011101001
01001101000010000111010
10000111010100001001001
11010001010101101010010
10110100000110101010010
11010010010001101000000
00110100000011101010010
10101011101000010011101
00101010101010101110100
00101010111010000101000
10111010001010011010010
00010100110100101001001
10100100010110101000101
11010010010101110100101
00011101010010100100111
01010101000011010010101
01011101010010001011010
10000101101010001001101
01010101000101101001010
10010010110101001001011
10101010010101110101001
01001101010100001110100
01001001010111010101001
01011101010100000111010
10010000011010101010010
11101010010101101000100
10001110100000001110100
10100101010101110100101
00100101011101000001010
11101000010001110100000
10101001110100001010011
10100000100010111010001
00001110100001001010011
10100010000101101000101
00101110100010100101101
00100000101101000101010
01001101000101010101110
10010000011101001001010
10101110101010100110100
10001010110100100100101
10100000001011010000010
00110100000100101101000
00000011010010100010111
01001010100011010010100
10101101000001001110100
10101001011010010011101
01000000101011101010000
00110101010001010101101
00101010110101000010101
11010100100101011101010
00100101101010010000101
11010000001110101001000
10110101001010011010101
00010111010100101001011
10101010000010111010101
00000101110100000011101
01010000101011101001010
10110101010000101110101
00010101011101010100100
10111010101010000111010
10000000111010010010000
11010010010001011010101
01010011101000000001011
01001000011010101010100
10111010010000110100100
01010101110100001000111
01000100001110100001101
00000001011010000010010
11101010100101010110100
01000100101110100000100
11101010100110100000101
01011010000100001110100
10000100011101010101010
10011101000010010011101
00010010000111010000101
00101101000010100001110
10101010101011101000100
10011010001001001101010
01010010111010001000101
01110100000001110100010
01001011101001101001001
00001011010101010011010
00101000101110100001101
01000010001011010100110
10101001010010110101010
01101001001010111010011
01001000001011010001010
10100011101001000010101
10100000010011010010001
00101110100100001101010
00001001011101001001010
01101001001010101101001
10100100101001011010011
01001010000010110100100
00011101010010011010101
01000010111010010100001
01110100101010101110101
00010010110100100111010
01010100010111010001001
11010100001011010010011
10100101010101011101001
00011101001010101001011
10100100011101010000010
10101110011010100000101
10100100111010100000010
11101001011010100000101
01101001010010111010100
00100101110100001101010
00100001011010100110101
00010001011010101010010
11101010001010010110100
01010101011101001000010
10110101000101110101001
00101010111010101001001
01110101000111010100011
10101001001001011101010
00111010100101000101110
10100010111010100001001
01110101000111010001010
00101110100101001011101
01001010100101110100101
01010101011010100001010
10101101000010011101000
01010101010111010101000
10101110101010001010111
01000000111010101000100
10111010000001110101010
01000101110101000000110
10100001011010000001110
10010000001011101010001
11010100100010101110101
00110101010100010101101
00000110101010100101010
11010000001001101010101
00100111010100110101010
10010010110101001101001
00100111010000011010101
01010010101101010001001
10100010100101010111010
00001101010101010100101
10100010001110100010101
01010101101000100011101
00001010111010001001000
01110100110100000001001
11010000001001011101000
10001010011101000000100
10111010010101010100101
10100001010101011101000
10010100101110100000100
01011101010100101101000
10001001110100000100101
01110100000010101011010
00010001110011110100001
00000111010000100100111
01000001010010111010000
01010010110100001000101
01110100001000100110100
01000011101011110100001
00100101110100001001001
01110100000001010111010
00010101000110100010010
11101000010000011101000
01001110100010000010111
01010100101101000100000
10111010000101010101110
10000001010101110100010
00010101110100010000101
01110100100000111010100
10010011010000001010111
01000100010010111010101
00001110101001010110100
10101010000110100000101
00110100000001110100000
10010011101001011010010
00101001011010101001101
00010100100101101010100
11010001010100010110011
01010010010111010101001
10100010101010101100110
10100010101011001101001
00010101010111010001000
11101001001010101010110
10010100101000110100100
00001011101000001101010
10010101010110100101010
11010010001000101110100
01010101101010000010101
10100010000011010010001
01011010000100111010100
10101010101110100101101
00100100010101100110100
10010010101011101001101
00100100101011010010110
10010010010010110100101
10100100101000101100110
10010010100101011101000
10101110100100101110011
01001001010100101110011
01001010001010101110100
01000111010000101001011
01001010001011101001010
00101011010001001110100
10100010010111010001001
11010010100100010111001
10100100010001110100010
01110100101001010101110
01101001010000011100110
10101010101101000000011
10100101010010101011101
00100011101001010100101
01110011010000101001001
10011010100000110100000
00111010010101010010101
11001101010001000011010
00000011101000100101010
10111010001000111010101
01010101010110100001001
11010010001001010111010
01010100010011010100000
00101101001001110101000
01010111010010000110101
00000001011010010001110
10100100101110100001101
01000010101011010100010
11101010000101001011101
01000101110101000101010
10111001101010001010110
100001101010001001010
Пытливый читатель, вооруженный эффективным домашним компьютером, быть может захочет проверить, используя данные в тексте предписания и применяя эту последовательность к номерам различных простых машин Тьюринга, что она и в самом деле соответствует универсальной машине Тьюринга! Некоторое уменьшение величины и может быть достигнуто за счет другого определения машины Тьюринга. Например, мы могли бы отказаться от использования команды STOP и вместо этого применять правило остановки после того, как машина повторно возвращается во внутреннее состояние 0 из какого-либо другого внутреннего состояния. Это не дало бы нам значительного выигрыша (а может, и вовсе никакого). Большую пользу принесло бы использование лент с иными, нежели только 0 и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчива, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.
49
Напомним, что натуральными мы называем числа 0,1,2,3,4,5,6… Вместо обычной записи (xω+yω = zω, где х, у, z > 0, ω > 2) мы используем «х + 1», «ω + 3» и т. д., чтобы включить в рассмотрение все натуральные числа, начиная с нуля.
50
Желающие ознакомиться с вопросами, имеющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратиться к работе Дэвлина [1988].
51
Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред.
52
Напомним, что простые числа 2, 3, 5, 7, 11, 13, 17… - это такие натуральные числа, которые делятся только на самих себя и на единицу. Ни нуль, ни единица простыми числами не считаются.