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

Пенроуз Роджер

…001101100…

Тогда исходный набор из шести чисел может быть записан в двоичной форме как

101,1101''1,1,100,

и на ленте при кодировании в расширенной двоичной форме мы получим последовательность

…00001001011010100101101101011010110100011000.,

в которой на один нуль меньше по сравнению с предыдущим кодом того же набора.

Теперь мы можем рассмотреть машину Тьюринга, реализующую, скажем, алгоритм Евклида в применении к паре чисел, записанных в расширенной бинарной форме. Для примера возьмем ту же пару чисел — 6 и 8, которую мы брали ранее. Вместо прежней унарной записи

…0000011111101111111100000…

воспользуемся двоичным представлением 6 и 8, т. е. 110 и 1000, соответственно. Тогда эта параимеет

вид

6, 8, или в двоичной форме 110, 1000,

и в расширенной двоичной записи на ленте она будет выглядеть следующим образом

… 00000101001101000011000000….

Для этой конкретной пары чисел двоичная форма записи не дает никакого выигрыша по сравнению с унарной. Предположим, однако, что мы берем для вычислений (десятичные) числа 1 583 169 и 8610. В двоичной записи они имеют вид

110000010100001000001,

10000110100010.

На ленте при расширенном двоичном кодировании им будет соответствовать последовательность

… 001010000001001000001000000101101000001010010000100110

которая занимает менее двух строк, тогда как для унарной записи пары чисел «1 583 169, 8610» не хватило бы места на страницах этой книги!

Машину Тьюринга, выполняющую алгоритм Евклида для чисел, записанных в расширенной двоичной форме, при желании можно получить из EUCс помощью пары дополнительных алгоритмов, которые переводили бы числа из расширенной двоичной формы в унарную и обратно. Однако, такой подход чрезвычайно неэффективен, ибо громоздкость унарной системы записи была бы по-прежнему «внутренне» присуща всему устройству, что проявилось бы в его низком быстродействии и потребности в огромном количестве «черновиков» (на левой стороне ленты). Можно построить и более эффективную машину Тьюринга для алгоритма Евклида, оперирующую исключительно расширенными двоичными числами, но для понимания принципов ее работы это не особенно важно.

Для того чтобы показать, каким образом машина Тьюринга может работать с числами в расширенном двоичном представлении, обратимся к значительно более простой, чем алгоритм Евклида, процедуре — просто прибавлению единицык произвольному натуральному числу. Ее можно выполнить с помощью следующей машины Тьюринга (которую я назову XN + 1):

0 0– > 0 0R

0 1– > 1 1R

1 0– > 0 0R

1 1– > 10 1R

10 0– > 11 0L

10 1– > 10 1R

11 0– > 10 1.STOP

11 1– > 100 0L

100 0– > 101 1L

100 1– > 100 1L

101 0– > 110 0R

101 1– > 10 1R

110 1– > 111 1R

111 0– > 11 1R

111 1– > 111 0R

И вновь некоторые дотошные читатели могут захотеть проверить, вправду ли эта машина Тьюринга действует так, как должна, если взять, скажем, число 167. Это число имеет двоичное представление 10100111и записывается на ленте как

…0000100100010101011000…

Чтобы прибавить единицу к двоичному числу, мы просто находим в его записи последний нуль и меняем его на единицу, а все непосредственно следующие за ним единицы — на нули. Так что

167 + 1 = 168

в двоичной форме записывается в виде

10100111 + 1 = 10101000.

Таким образом, наша «прибавляющая единицу» машина Тьюринга должна превратить предыдущую запись на ленте в

… 0000100100100001100000

что она и делает.

Обратите внимание, что даже самая простая операция прибавления единицы в такой записи выглядит

довольно сложно, включая в себя 15 инструкций и восемь различных внутренних состояний! Конечно, в случае унарной записи все было значительно проще, поскольку тогда «прибавление единицы» означало удлинение строчки единиц еще на одну, поэтому не удивительно, что машина UN +1была более простой. Однако, для очень больших чисел UN + 1была бы слишком медленной из-за чрезмерной длины ленты, и тогда более сложная машина XN + 1, но работающая с более компактным расширенным двоичным представлением, оказалась бы предпочтительнее.

Несколько отступая в сторону, я укажу операцию, для которой машина Тьюринга проще в расширенной двоичной, нежели в унарной форме — это умножение на два. Действительно, машина Тьюринга XN х 2, заданная в виде

0 0– > 0 0R

0 1– > 1 0R

1 0– > 0 1R

1 1– > 10 0R

10 0– > 11 1R

11 0– > 0 1.STOP

запросто выполнит эту операцию в расширенной двоичной форме, тогда как соответствующая унарная машина UN х 2, описанная ранее, гораздо сложнее!

Этот раздел дает определенное представление о том, на что способны в простейших случаях машины Тьюринга. Как и следовало ожидать, при выполнении более или менее сложных операций эти машины могут становиться, и действительно становятся, несравненно более сложными. Каковы же принципиальные возможности таких устройств? Мы рассмотрим этот вопрос в следующем параграфе.

Тезис Черча — Тьюринга

После ознакомления с принципами построения простых машин Тьюринга легко убедиться, что все основные математические операции, такие как сложение двух чисел, их перемножение или возведение одного из них в степень другого, могут на самом деле быть выполнены соответствующими машинами Тьюринга. Построение таких машин в явном виде не представляет больших затруднений, но я не собираюсь сейчас этим заниматься. Машины Тьюринга могут выполнять операции, результат которых выражается парой натуральных чисел, например, деление с остатком, или сколь угодно большим, но конечным множеством чисел. Более того, можно сконструировать такие машины Тьюринга, для которых арифметические операции не предопределены заранее, а могут задаваться инструкциями, вводимыми с ленты. При этом возможно, что та конкретная операция, которая должна быть выполнена, будет зависеть в тот или иной момент от результатов вычислений, которые машина должна была выполнить на предыдущих этапах. («Если результат вычислений больше, чем то-то, надо сделать то-то, в противном случае выполнить то-то».) Убедившись, что можно построить машины Тьюринга, выполняющие арифметические или простые логические операции, уже не так трудно представить себе, какими должны быть машины, выполняющие более сложные задачи алгоритмического характера. «Повозившись» немного с подобными задачами, легко приходишь к убеждению в том, что машина этого типа может выполнять вообще любые механические операции! Тогда с точки зрений математики приобретает смысл определениемеханической операции как такой операции, которую может выполнить подобная машина. Существительное «алгоритм» и прилагательные «вычислимый», «рекурсивный» и «эффективный» используются математиками для обозначения механических операций, которые могут быть выполнены теоретическими устройствами такого рода, т. е. машинами Тьюринга. Если некоторая процедура четко определена и по природе своей механистична, то можно вполне обоснованно предположить, что найдется машина Тьюринга, способная ее выполнить. Это, в конце концов, и есть основной момент наших (то есть Тьюринга) рассуждений, лежащий и в основе самой концепции машины Тьюринга.