Доказательство Тьюринга — это доказательство Алана Тьюринга , впервые опубликованное в ноябре 1936 года [1] под названием « О вычислимых числах с приложением к Entscheidungsproblem ». Это было второе доказательство (после теоремы Чёрча ) отрицания Entscheidungsproblem Гильберта ; то есть гипотезы о том, что на некоторые чисто математические вопросы типа «да-нет» никогда нельзя ответить с помощью вычислений; более технически, что некоторые проблемы принятия решений « неразрешимы » в том смысле, что не существует единого алгоритма, который безошибочно даёт правильный ответ «да» или «нет» для каждого случая проблемы. По словам самого Тьюринга: «то, что я докажу, сильно отличается от известных результатов Гёделя... Теперь я покажу, что не существует общего метода, который бы говорил, доказуема ли данная формула U в K [ Principia Mathematica ]». [2]
Тьюринг последовал за этим доказательством двумя другими. Второе и третье оба опираются на первое. Все они опираются на его разработку «вычислительных машин», подобных пишущим машинкам, которые подчиняются простому набору правил, и на его последующую разработку «универсальной вычислительной машины».
В своем доказательстве того, что Entscheidungsproblem не может иметь решения, Тьюринг исходил из двух доказательств, которые должны были привести к его окончательному доказательству. Его первая теорема наиболее релевантна проблеме остановки , вторая — теореме Райса .
Первое доказательство : не существует «вычислительной машины», которая могла бы решить, является ли произвольная «вычислительная машина» (представленная целым числом 1, 2, 3, . . .) «бескруговой» (т. е. продолжает печатать свое число в двоичном коде до бесконечности): «... у нас нет общего процесса, чтобы сделать это за конечное число шагов» (стр. 132, там же ). Доказательство Тьюринга, хотя оно, кажется, использует «диагональный процесс», на самом деле показывает, что его машина (называемая H) не может вычислить свое собственное число, не говоря уже о всем диагональном числе ( диагональный аргумент Кантора ): «Ошибка в аргументе заключается в предположении, что B [диагональное число] вычислимо» [3] Доказательство не требует много математики.
Второе доказательство : Это доказательство, возможно, более знакомо читателям как теорема Райса : «Мы можем показать далее, что не может быть машины E, которая, будучи снабжена SD [«программой»] произвольной машины M, будет определять, напечатает ли M когда-либо заданный символ (скажем, 0) » [a]
Третье доказательство : «Соответствуя каждой вычислительной машине M, мы строим формулу Un(M) и показываем, что если существует общий метод определения того, доказуема ли Un(M), то существует общий метод определения того, печатает ли M когда-либо 0». [2]
Третье доказательство требует использования формальной логики для доказательства первой леммы, за которым следует краткое словесное доказательство второй:
Лемма 1: Если S1 [символ «0»] появляется на ленте в некоторой полной конфигурации M, то Un(M) доказуемо. [4]
Лемма 2: [Обратное] Если Un(M) доказуемо, то S1 [символ «0»] появляется на ленте в некоторой полной конфигурации M. [5]
Наконец, всего лишь в 64 словах и символах Тьюринг доказывает методом сведения к абсурду, что «проблема Гильберта Entscheidungsproblem не может иметь решения» [2] .
Тьюринг создал целую чащу сокращений. Определения см. в глоссарии в конце статьи.
Некоторые важные пояснения:
Машина Тьюринга H пытается напечатать диагональное число из нулей и единиц.
Это диагональное число создается, когда H фактически «моделирует» каждую «успешную» оцениваемую машину и выводит R-ю «цифру» (1 или 0) R-й «успешной» машины.
Тьюринг посвятил большую часть своей статьи фактическому «построению» своих машин, чтобы убедить нас в их истинности. Это было необходимо для использования им формы доказательства reductio ad absurdum . Мы должны подчеркнуть «конструктивную» природу этого доказательства. Тьюринг описывает то, что могло бы быть реальной машиной, действительно построимой. Единственный сомнительный элемент — это существование машины D, которую это доказательство в конечном итоге покажет как невозможную.
Тьюринг начинает доказательство с утверждения о существовании машины «решения/определения» D. Если подать на нее любую SD (строку символов A, C, D, L, R, N, точку с запятой «;»), она определит, представляет ли эта SD (строка символов) «вычислительную машину», которая является либо «круговой» — и, следовательно, «неудовлетворительной u», либо «без кругов» — и, следовательно, «удовлетворительной s».
Ранее Тьюринг продемонстрировал в своих комментариях, что все «вычислительные машины» — машины, которые вычисляют числа как единицы и нули вечно — могут быть записаны в виде SD на ленте «универсальной машины» U. Большая часть его работы, предшествовавшей его первому доказательству, была посвящена демонстрации того, что универсальная машина действительно существует, т. е.
Действительно существует универсальная машина U
Для каждого числа N действительно существует уникальная SD,
У каждой машины Тьюринга есть SD
Каждая SD на ленте U может быть «запущена» U и даст тот же «выход» (цифры 1, 0), что и исходная машина.
Тьюринг не комментирует, как машина D выполняет свою работу. Ради аргумента предположим, что D сначала посмотрит, является ли строка символов «правильно сформированной» (т. е. в форме алгоритма, а не просто набора символов), и если нет, то отбросит ее. Затем она начнет «охоту за кругами». Для этого, возможно, она будет использовать «эвристики» (трюки: обученные или изученные). Для целей доказательства эти детали не важны.
Затем Тьюринг описывает (довольно вольно) алгоритм (метод), которому должна следовать машина, которую он называет H. Машина H содержит в себе машину принятия решений D (таким образом, D является «подпрограммой» H). Алгоритм машины H выражен в таблице инструкций H или, возможно, в Стандартном описании H на ленте и объединен с универсальной машиной U; Тьюринг не уточняет этого.
В ходе описания универсальной машины U Тьюринг продемонстрировал, что SD машины (строка букв, похожая на «программу») может быть преобразована в целое число (по основанию 8) и наоборот. Любое число N (по основанию 8) может быть преобразовано в SD со следующими заменами: 1 на A, 2 на C, 3 на D, 4 на L, 5 на R, 6 на N, 7 на точку с запятой «;».
Как оказалось, уникальный номер (DN) машины H — это число «K». Мы можем сделать вывод, что K — это какое-то очень длинное число, может быть, в десятки тысяч цифр. Но это неважно для дальнейшего.
Машина H отвечает за преобразование любого числа N в эквивалентную строку символов SD для проверки подмашиной D. (На языке программирования: H передает произвольное «SD» в D, а D возвращает «удовлетворительно» или «неудовлетворительно».) Машина H также отвечает за ведение подсчета R («Record»?) успешных чисел (мы предполагаем, что число «успешных» SD, т. е. R, намного меньше числа протестированных SD, т. е. N). Наконец, H печатает на участке своей ленты диагональное число «бета-штрихованное» B'. H создает это B', «симулируя» (в компьютерном смысле) «движения» каждой «удовлетворительной» машины/числа; в конечном итоге эта тестируемая машина/число достигнет своей R-й «цифры» (1 или 0), и H напечатает ее. Затем H отвечает за «уборку беспорядка», оставленного симуляцией, увеличивая N и продолжая свои тесты, и так до бесконечности .
Примечание: Все эти машины, за которыми охотится H, — это то, что Тьюринг называл «вычислительными машинами». Они вычисляют двоично-десятичные числа в бесконечном потоке того, что Тьюринг называл «цифрами»: только символы 1 и 0.
Пример: Предположим, что машина H проверила 13472 числа и выдала 5 удовлетворительных чисел, т. е. H преобразовала числа от 1 до 13472 в SD (строки символов) и передала их в D для проверки. В результате H подсчитала 5 удовлетворительных чисел и довела первое до первой «цифры», второе до второй, третье до третьей, четвертое до четвертой и пятое до пятой. Теперь счет составляет N = 13472, R = 5 и B' = «.10011» (например). H убирает беспорядок на своей ленте и продолжает:
H увеличивает N = 13473 и преобразует "13473" в строку символов ADRLD. Если подмашина D считает ADLRD неудовлетворительным, то H оставляет запись подсчета R на 5. H увеличит число N до 13474 и продолжит работу. С другой стороны, если D считает ADRLD удовлетворительным, то H увеличит R до 6. H преобразует N (снова) в ADLRD [это всего лишь пример, ADLRD, вероятно, бесполезен] и "запустит" его с помощью универсальной машины U, пока эта тестируемая машина (U "запускает" ADRLD) не напечатает свою 6-ю "цифру", т. е. 1 или 0. H напечатает это 6-е число (например, "0") в области "выход" своей ленты (например, B' = ".100110").
H наводит порядок, а затем увеличивает число N до 13474.
Весь процесс распутывается, когда H достигает своего собственного числа K. Продолжим наш пример. Предположим, что успешный подсчет/запись R составляет 12. H наконец достигает своего собственного числа минус 1, т. е. N = K-1 = 4335...321 4 , и это число оказывается неудачным. Затем H увеличивает N, чтобы получить K = 4355...321 5 , т. е. свое собственное число. H преобразует это в «LDDR...DCAR» и передает его машине принятия решений D. Машина принятия решений D должна вернуть «удовлетворительно» (то есть: H по определению должен продолжать и продолжать тестирование до бесконечности , потому что он «без кругов»). Поэтому теперь H увеличивает подсчет R с 12 до 13, а затем снова преобразует тестируемое число K в его SD и использует U для его моделирования. Но это означает, что H будет моделировать свои собственные движения. Что первым делом сделает моделирование? Эта симуляция K-aka-H либо создает новый N, либо «сбрасывает» «старый» N до 1. Этот «K-aka-H» либо создает новый R, либо «сбрасывает» «старый» R до 0. Old-H «запускает» новый «K-aka-H», пока не достигнет своей 12-й цифры.
Но он никогда не доходит до 13-й цифры; K-aka-H в конечном итоге снова достигает 4355...321 5 , и K-aka-H должен повторить тест. K-aka-H никогда не достигнет 13-й цифры. Машина H, вероятно, просто печатает копии себя до бесконечности на чистой ленте. Но это противоречит предпосылке, что H является удовлетворительной, некруглой вычислительной машиной, которая продолжает печатать 1 и 0 диагональных чисел вечно. (Мы увидим то же самое, если N сбросить на 1, а R сбросить на 0.)
Если читатель не верит этому, он может написать «заглушку» для машины принятия решений D (заглушка «D» вернет «удовлетворительно»), а затем посмотреть самостоятельно, что произойдет в тот момент, когда машина H столкнется со своим собственным числом.
Текст объемом менее одной страницы, переход от посылок к заключению неясен.
Тьюринг действует методом сведения к абсурду . Он утверждает существование машины E, которая при задании SD (стандартного описания, т. е. «программы») произвольной машины M определит, напечатает ли M когда-либо заданный символ (скажем, 0). Он не утверждает, что эта M является «вычислительной машиной».
Учитывая существование машины E, Тьюринг поступает следующим образом:
Трудность доказательства — шаг 1. Читателю будет полезно понять, что Тьюринг не объясняет свою тонкую работу. (В двух словах: он использует определенные эквивалентности между «экзистенциальными» и «универсальными операторами» вместе с их эквивалентными выражениями, записанными с помощью логических операторов.)
Вот пример: предположим, что мы видим перед собой парковку, полную сотен автомобилей. Мы решаем обойти всю парковку в поисках: «Автомобилей со спущенными (плохими) шинами». Примерно через час мы нашли две «машины с плохими шинами». Теперь мы можем с уверенностью сказать, что «У некоторых автомобилей плохие шины». Или мы могли бы сказать: «Неверно, что «У всех автомобилей хорошие шины». Или: «Верно, что: «не у всех автомобилей хорошие шины». Давайте перейдем к другой парковке. Здесь мы обнаруживаем, что «У всех автомобилей хорошие шины». Мы могли бы сказать: «Нет ни одного случая, чтобы у автомобиля были плохие шины». Таким образом, мы видим, что если мы можем сказать что-то о каждой машине в отдельности, то мы можем сказать что-то и обо ВСЕХ из них вместе.
Вот что делает Тьюринг: из M он создает набор машин { M 1, M 2, M 3, M 4, ..., Mn } и о каждой он пишет предложение: « X печатает по крайней мере один 0» и допускает только два « значения истинности », True = пробел или False = :0:. По одному он определяет значение истинности предложения для каждой машины и создает строку пробелов или :0:, или некоторую их комбинацию. Мы можем получить что-то вроде этого: « M 1 печатает 0» = True AND « M 2 печатает 0» = True AND « M 3 печатает 0» = True AND « M 4 печатает 0» = False, ... AND « Mn печатает 0» = False. Он получает строку
BBB:0::0::0: ... :0: ... до бесконечности
если существует бесконечное число машин Mn . Если, с другой стороны, если бы каждая машина выдавала «Истину», то выражение на ленте было бы
ББББ....ББББ... до бесконечности
Таким образом, Тьюринг преобразовал утверждения о каждой машине, рассматриваемой отдельно, в одно «утверждение» (строку) обо всех них. Учитывая машину (он называет ее G), которая создала это выражение, он может проверить ее с помощью своей машины E и определить, выдает ли она когда-либо 0. В нашем первом примере выше мы видим, что это действительно так, поэтому мы знаем, что не все M в нашей последовательности выводят 0. Но второй пример показывает, что, поскольку строка пустая, то каждое Mn в нашей последовательности выдает 0.
Все, что осталось сделать Тьюрингу, — это разработать процесс создания последовательности Mn из одного M.
Предположим, что M печатает этот шаблон:
Тьюринг создает еще одну машину F, которая берет M и выдает последовательность Mn, которые последовательно преобразуют первые n нулей в «0-bar» ( 0 ):
Он утверждает, не раскрывая подробностей, что эта машина F действительно может быть построена. Мы видим, что может произойти одно из двух. У F могут закончиться машины с нулями, или ей, возможно, придется до бесконечности создавать машины, чтобы «отменить нули».
Теперь Тьюринг объединяет машины E и F в составную машину G. G начинает с исходной M, затем использует F для создания всех машин-последователей M1, M2,. . ., Mn. Затем G использует E для проверки каждой машины, начиная с M. Если E обнаруживает, что машина никогда не печатает ноль, G печатает :0: для этой машины. Если E обнаруживает, что машина печатает 0 (мы предполагаем, Тьюринг этого не говорит), то G печатает :: или просто пропускает эту запись, оставляя квадраты пустыми. Мы видим, что может произойти пара вещей.
G не будет печатать 0 вообще, если все Mn печатают 0, ИЛИ
G будет печатать 0 до бесконечности, если все M не печатают 0, ИЛИ
G будет печатать 0 некоторое время, а затем остановится.
А что же происходит, когда мы применяем E к самому G?
Если E(G) определяет, что G никогда не печатает 0, то мы знаем, что все Mn печатают 0. И это означает, что, поскольку все Mn произошли от M, то M сама печатает 0 до бесконечности , ИЛИ
Если E(G) определяет, что G печатает 0, то мы знаем, что не все Mn печатают 0; следовательно, M не печатает 0 до бесконечности .
Поскольку мы можем применить тот же процесс для определения того, печатает ли M 1 бесконечно часто. Когда мы объединяем эти процессы, мы можем определить, продолжает ли M печатать 1 и 0 до бесконечности или нет . Таким образом, у нас есть метод определения того, является ли M свободным от кругов. Согласно Доказательству 1 это невозможно. Поэтому первое утверждение о том, что E существует, неверно: E не существует.
Здесь Тьюринг доказывает, «что проблема Гильберта Entscheidungsproblem не может иметь решения». [2] Здесь он
…показать(и), что не может быть общего процесса для определения того, является ли данная формула U функционального исчисления K доказуемой. ( там же ).
Обе леммы № 1 и № 2 необходимы для формирования необходимого «ЕСЛИ И ТОЛЬКО ЕСЛИ» (т.е. логической эквивалентности ), требуемого доказательством:
Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы (Франзен, стр. 67)
Тьюринг демонстрирует существование формулы Un (M), которая, по сути, гласит, что «в некоторой полной конфигурации M на ленте появляется 0 » (стр. 146). Эта формула ИСТИННА, то есть она «конструируема», и он показывает, как это сделать.
Затем Тьюринг доказывает две леммы, первая из которых требует всей тяжелой работы. (Вторая является обратной по отношению к первой.) Затем он использует reductio ad absurdum, чтобы доказать свой окончательный результат:
[Если читатели намерены подробно изучить доказательство, им следует исправить свои копии страниц третьего доказательства с помощью исправлений, предоставленных Тьюрингом. Читатели также должны иметь солидную подготовку по (i) логике (ii) статье Курта Гёделя : « О формально неразрешимых предложениях Principia Mathematica и связанных с ними системах ». [b] За помощью по статье Гёделя они могут обратиться, например, к книге Эрнеста Нагеля и Джеймса Р. Ньюмана « Доказательство Гёделя» , New York University Press, 1958.]
Чтобы следить за техническими подробностями, читателю необходимо понимать определение слова «доказуемый» и знать важные «подсказки».
«Доказуемость» означает, в смысле Гёделя, что (i) сама система аксиом достаточно мощна, чтобы произвести (выразить) предложение «Это предложение доказуемо», и (ii) что в любом произвольном «правильно построенном» доказательстве символы ведут посредством аксиом, определений и подстановок к символам заключения.
Первая подсказка: «Давайте приведем описание M к первой стандартной форме §6». Раздел 6 описывает весьма специфическое «кодирование» машины M на ленте «универсальной машины» U. Это требует от читателя знания некоторых особенностей универсальной машины Тьюринга U и схемы кодирования.
(i) Универсальная машина — это набор «универсальных» инструкций, которые находятся в «таблице инструкций». Отдельно от этого, на ленте U, «вычислительная машина» M будет находиться как «M-код». Универсальная таблица инструкций может печатать на ленте символы A, C, D, 0, 1, u, v, w, x, y, z, : . Различные машины M могут печатать эти символы только косвенно, приказав U напечатать их.
(ii) «Машинный код» M состоит всего из нескольких букв и точки с запятой, т. е. D, C, A, R, L, N, ; . Нигде в «коде» M не появятся числовые «цифры» (символы) 1 и 0. Если M хочет, чтобы U напечатал символ из набора пробелов, 0, 1 , то он использует один из следующих кодов, чтобы сообщить U о необходимости их печати. Чтобы все было еще более запутанным, Тьюринг называет эти символы S0, S1 и S2, т. е.
(iii) «Вычислительная машина», встроена ли она непосредственно в таблицу (как показывают его первые примеры) или в виде машинного кода М на ленте универсальной машины U, печатает свой номер на чистой ленте (справа от М-кода, если он есть) в виде единиц и нулей , непрерывно перемещающихся вправо.
(iv) Если "вычислительная машина" - это U+"M-код", то "M-код" появляется первым на ленте; лента имеет левый конец, и "M-код" начинается там и продолжается направо на альтернативных квадратах. Когда M-код подходит к концу (а это должно быть, поскольку предполагается, что эти M-коды являются конечными алгоритмами), "цифры" начнутся как 1 и 0 на альтернативных квадратах, продолжаясь направо вечно. Тьюринг использует (пустые) альтернативные квадраты (называемые "E"- "стираемыми"- квадратами), чтобы помочь U+"M-коду отслеживать, где находятся вычисления, как в M-коде, так и в "цифрах", которые печатает машина.
(v) «Полная конфигурация» — это печать всех символов на ленте, включая М-код и «цифры» до этого момента, вместе с текущей сканируемой цифрой (с указателем-символом, напечатанным слева от сканируемого символа?). Если мы правильно поняли смысл Тьюринга, это будет чрезвычайно длинный набор символов. Но неясно, должен ли повторяться весь М-код; необходима только печать текущей инструкции М-кода плюс печать всех цифр с маркером цифры).
(vi) Тьюринг сократил огромное возможное количество инструкций в «М-коде» (опять же: код M, который должен появиться на ленте) до небольшого канонического набора, одного из трех, похожего на этот: {qi Sj Sk R ql} например, если машина выполняет инструкцию #qi и символ Sj находится на сканируемом квадрате, то напечатать символ Sk и перейти направо, а затем перейти к инструкции ql : Другие инструкции аналогичны, кодируя «влево» L и «нет движения» N. Именно этот набор кодируется строкой символов qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A. Каждая инструкция отделяется от другой точкой с запятой. Например, {q5, S1 S0 L q3} означает: Инструкция № 5: если сканируемый символ равен 0 , то напечатать пробел , перейти налево, затем перейти к инструкции № 3. Она кодируется следующим образом
; ДАААААДКДЛДАА
Вторая подсказка: Тьюринг использует идеи, представленные в статье Гёделя, то есть «Гёделизацию» (по крайней мере, части) формулы для Un (M). Эта подсказка появляется только в виде сноски на странице 138 (Davis (1965), стр. 138): «Последовательность из r простых чисел обозначается ^ (r)» ( там же ). [Здесь r внутри скобок «возведено».] Эта «последовательность простых чисел» появляется в формуле, называемой F^(n).
Третья подсказка: Это усиливает вторую подсказку. Первоначальная попытка доказательства Тьюринга использует выражение:
(Eu)N(u) & (x)(... и т.д. ...) [6]
Ранее в статье Тьюринг уже использовал это выражение (стр. 138) и определил N(u) как «u — неотрицательное целое число» ( там же ) (т. е. число Гёделя). Но с поправками Бернайса Тьюринг отказался от этого подхода (т. е. от использования N(u)) и единственное место, где «число Гёделя» появляется явно, — это где он использует F^(n).
Что это значит для доказательства? Первая подсказка означает, что простая проверка M-кода на ленте не покажет, печатается ли когда-либо символ 0 с помощью U+"M-код". Тестовая машина может искать появление DC в одной из строк символов, представляющих инструкцию. Но будет ли эта инструкция когда-либо "выполнена"? Что-то должно "запустить код", чтобы узнать. Это что-то может быть машиной, или это могут быть строки в формальном доказательстве, т. е. Лемма № 1.
Вторая и третья подсказки означают, что доказательство затруднительно, поскольку его основой является работа Гёделя.
В примере ниже мы фактически построим простую «теорему» — небольшую программу Post–Turing machine «запустим ее». Мы увидим, насколько механической может быть правильно разработанная теорема. Доказательство, как мы увидим, — это всего лишь «тест» теоремы, который мы делаем, вставляя «пример доказательства» в начало и смотря, что получится в конце.
Обе леммы № 1 и № 2 необходимы для формирования необходимого «ЕСЛИ И ТОЛЬКО ЕСЛИ» (т.е. логической эквивалентности), требуемого доказательством:
Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы. (Франзен, стр. 67)
Процитирую Францена:
Говорят, что предложение A разрешимо в формальной системе S, если либо A, либо его отрицание доказуемо в S. (Франзен, стр. 65)
Ранее в своей книге Францен определил понятие «доказуемость»:
Формальная система — это система аксиом (выраженных на некотором формально определенном языке) и правил рассуждения (также называемых правилами вывода), используемых для вывода теорем системы. Теорема — это любое утверждение на языке системы, получаемое путем ряда применений правил рассуждения, начиная с аксиом. Доказательство — это конечная последовательность таких применений, приводящая к теореме как ее заключению. ( там же, с. 17)
Таким образом, «предложение» — это цепочка символов, а теорема — это цепочка цепочек символов.
Перед Тьюрингом стоит следующая задача:
преобразовать «программу» универсальной машины Тьюринга и числовые символы на ленте («цифры» Тьюринга, символы «1» и «0») в «теорему», то есть (чудовищно длинную) строку предложений , определяющих последовательные действия машины, (все) цифры на ленте и местоположение «головки ленты».
Таким образом, «строка предложений» будет строками строк символов. Единственные разрешенные отдельные символы будут взяты из символов Гёделя, определенных в его статье. (В следующем примере мы используем «<» и ">» вокруг «фигуры», чтобы указать, что «фигурой» является символ, сканируемый машиной).
Далее мы должны напомнить себе, что каждая из «вычислительных машин» Тьюринга — это генератор/создатель двоичных чисел, который начинает работу с «чистой ленты». Правильно построенная, она всегда крутится до бесконечности, но ее инструкции всегда конечны. В доказательствах Тьюринга лента Тьюринга имела «левый конец», но расширенный правый до бесконечности. Для примера ниже мы предположим, что «машина» — это не Универсальная машина, а скорее более простая «специализированная машина» с инструкциями в Таблице.
Наш пример основан на модифицированной модели машины Тьюринга Post–Turing . Эта модель печатает только символы 0 и 1. Чистая лента считается состоящей из всех b. Наша модифицированная модель требует от нас добавить еще две инструкции к 7 инструкциям Post–Turing. Сокращения, которые мы будем использовать, следующие:
R, ВПРАВО: посмотреть направо и переместить ленту влево или переместить головку ленты вправо
L, ВЛЕВО: посмотреть налево и переместить ленту вправо или переместить головку ленты влево
E, СТИРАТЬ отсканированный квадрат (например, сделать квадрат пустым)
P0: ПЕЧАТЬ 0 в отсканированном квадрате
P1: ПЕЧАТЬ 1 в отсканированном квадрате
Jb_n, ПЕРЕХОД-ЕСЛИ-пустой-к-инструкции_#n,
J0_n, ПЕРЕХОД-ЕСЛИ-0-к-инструкции_#n,
J1_n, ПЕРЕХОД-ЕСЛИ-1-к-инструкции_#n,
ОСТАНОВКА.
В случаях R, L, E, P0 и P1 после выполнения своей задачи машина переходит к следующей инструкции в числовой последовательности; то же самое касается переходов, если их тесты не пройдены.
Но для краткости в наших примерах будут использоваться только три квадрата. И они всегда будут начинаться как пробелы с отсканированным квадратом слева: т.е. bbb. С двумя символами 1, 0 и пробелом мы можем иметь 27 различных конфигураций:
ббб, бб0, бб1, б0б, б00, б01, б1б, б10, б11, 0бб, 0б0, 0б1, 00б, 000, 001, 01б, 010, 011, 1бб, 1б0, 1б1, 10б, 100, 101, 11б, 110, 111
Здесь нужно быть осторожными, потому что вполне возможно, что алгоритм (временно) оставит пробелы между фигурами, а затем вернется и что-то заполнит. Более вероятно, что алгоритм может сделать это намеренно. Фактически, машина Тьюринга делает это — она печатает на альтернативных квадратах, оставляя пробелы между фигурами, чтобы она могла печатать символы-локаторы.
Тьюринг всегда оставлял альтернативные квадраты пустыми, чтобы его машина могла поместить символ слева от цифры (или буквы, если машина является универсальной машиной и сканируемый квадрат на самом деле находится в «программе»). В нашем небольшом примере мы откажемся от этого и просто поместим символы ( ) вокруг сканируемого символа, как показано ниже:
b(b)0 это означает, "Лента пустая слева от левой пустой, но левая пустая находится "в игре", сканируемый квадрат пустой, "0", пробелы справа"
1(0)1 это означает, "Лента пустая слева, затем 1, сканируемый квадрат равен "0""
Давайте напишем простую программу:
начало: П1, Р, П1, Р, П1, Н
Помните, что мы всегда начинаем с чистой ленты. Полная конфигурация печатает символы на ленте, за которыми следует следующая инструкция:
начальная конфигурация: (b) P1,
конфигурация № 1: (1) R,
конфигурация № 2: 1(b) P1,
конфигурация № 3: 1(1) R,
конфигурация № 4: 11(b) P1,
конфигурация № 5: 11(1) H
Давайте добавим «прыжок» в формулу. Когда мы это сделаем, мы поймем, почему полная конфигурация должна включать символы ленты. (На самом деле, мы видим это лучше, ниже.) Эта маленькая программа печатает три «1» справа, меняет направление и движется влево, печатая 0, пока не наткнется на пробел. Мы напечатаем все символы, которые использует наша машина:
начало: П1, П, П1, П, П1, П0, Л, J1_7, Н
(б)бб П1,
(1)бб П,
1(б)б П1,
1(1)б П,
11(б) П1,
11(1) П0,
11(0) Л,
1(1)0 J1_7
1(1)0 Л
(1)10 J0_7
(1)10 Л
(б)110 J0_7
(б)110 Н
Здесь в конце мы обнаруживаем, что пробел слева «вошел в игру», поэтому мы оставляем его как часть общей конфигурации.
Учитывая, что мы выполнили свою работу правильно, мы добавляем начальные условия и смотрим, «куда движется теорема». Полученная конфигурация — число 110 — является ДОКАЗАТЕЛЬСТВОМ.
Доказательство Тьюринга осложнено большим количеством определений и запутано в том, что Мартин Дэвис назвал «мелкими техническими подробностями» и «... техническими подробностями, [которые] неверны в том виде, в котором они даны». [c] Сам Тьюринг опубликовал «Исправление» в 1938 году: «Автор обязан П. Бернейсу за указание на эти ошибки». [7]
В частности, в своей первоначальной форме третье доказательство сильно испорчено техническими ошибками. И даже после предложений Бернейса и исправлений Тьюринга ошибки остались в описании универсальной машины . И, что сбивает с толку, поскольку Тьюринг не смог исправить свою первоначальную статью, часть текста в тексте отсылает к некорректной первой попытке Тьюринга.
Исправления Бернейса можно найти в работе Дэвиса (1965), стр. 152–154; оригинал можно найти как «О вычислимых числах с приложением к проблеме Entscheidungsproblem. Исправление», Труды Лондонского математического общества (2), 43 (1938), 544–546.
В онлайн-версии статьи Тьюринга эти исправления содержатся в приложении; однако исправления к Универсальной машине можно найти в анализе, предоставленном Эмилем Постом .
Сначала единственным математиком, который уделил пристальное внимание деталям доказательства, был Пост (ср. Hodges, стр. 125) — в основном потому, что он одновременно пришел к похожему сокращению «алгоритма» до примитивных машиноподобных действий, поэтому он проявил личный интерес к доказательству. Как ни странно (возможно, помешала Вторая мировая война), Посту потребовалось около десяти лет, чтобы разобрать его в Приложении к своей статье «Рекурсивная неразрешимость проблемы Туэ» , 1947. [d]
Возникают и другие проблемы: в своем Приложении Пост косвенно прокомментировал сложность статьи и прямо ее «структурный характер» [e] и «интуитивную форму» доказательств. [e] Посту пришлось сделать несколько выводов:
Если наша критика верна, то говорят, что машина не имеет кругов, если она является вычислительной машиной Тьюринга, которая печатает бесконечное число нулей и единиц. И две рассматриваемые теоремы Тьюринга на самом деле следующие. Нет такой машины Тьюринга, которая при подаче произвольного положительного целого числа n определит, является ли n DN вычислительной машины Тьюринга, которая не имеет кругов. [Во-вторых], нет такой машины Тьюринга, которая при подаче произвольного положительного целого числа n определит, является ли n DN вычислительной машины Тьюринга, которая когда-либо печатает заданный символ (скажем, 0). [f]
Любой, кто когда-либо пытался прочитать эту газету, поймет жалобу Ходжеса:
Статья начиналась привлекательно, но вскоре (в типичной манере Тьюринга) погрузилась в дебри непонятного немецкого готического шрифта, чтобы разработать свою таблицу инструкций для универсальной машины. Последними, кто бросит на нее взгляд, были прикладные математики, которым пришлось прибегнуть к практическим вычислениям... (Ходжес, стр. 124)
1 вычислимое число — число, десятичная дробь которого вычисляется машиной (т.е. конечными средствами, такими как алгоритм)
2 M — машина с конечной таблицей инструкций и сканирующей/печатающей головкой. M перемещает бесконечную ленту, разделенную на квадраты, каждый из которых «способен нести символ». Машинные инструкции только следующие: переместиться на один квадрат влево, переместиться на один квадрат вправо, на сканированном квадрате напечатать символ p, стереть сканированный квадрат, если символ p, то выполнить инструкцию aaa, если сканированный символ не p, то выполнить инструкцию aaa, если сканированный символ отсутствует, то выполнить инструкцию aaa, если сканированный символ любой, то выполнить инструкцию aaa [где «aaa» — идентификатор инструкции].
3 вычислительная машина — М, которая печатает два вида символов, символы первого типа называются «цифрами» и представляют собой только двоичные символы 1 и 0; символы второго типа — любые другие символы.
4 цифры — символы 1 и 0 , они же «символы первого рода»
5 m-конфигурация — идентификатор инструкции, либо символ в таблице инструкций, либо строка символов, представляющая номер инструкции на ленте универсальной машины (например, «DAAAAA = #5»)
6 символов второго рода — любые символы, кроме 1 и 0
7 круговая — неудачная вычислительная машина. Она не может напечатать до бесконечности цифры 0 или 1 , которые представляют в двоичной системе число, которое она вычисляет
8 без круга — успешная вычислительная машина. Она печатает до бесконечности цифры 0 или 1 , которые представляют в двоичном виде число, которое она вычисляет
9 последовательность — как в «последовательности, вычисленной машиной»: символы первого рода, также известные как цифры, также известные как символы 0 и 1.
10 вычислимая последовательность — может быть вычислена с помощью машины без кругов
11 SD – Стандартное описание: последовательность символов A, C, D, L, R, N, «;» на ленте машины Тьюринга
12 DN — Описание числа : SD, преобразованное в число: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;
13 M(n) — машина, DN которой — число «n»
14 удовлетворительно — SD или DN, представляющие машину без кругов
15 U — машина, снабженная «универсальной» таблицей инструкций. Если U «снабдить лентой, на начале которой записан SD некоторой вычислительной машины M, то U вычислит ту же последовательность, что и M».
16 β' — «бета-примированный»: так называемое «диагональное число», составленное из n-й цифры (т. е. 0 или 1) n-й вычислимой последовательности [также: вычислимое число H, см. ниже]
17 у — неудовлетворительный, т.е. круговой, СД
18 с — удовлетворительно, т.е. СД без кругов
19 D — машина, содержащаяся в H (см. ниже). При поставке с SD любой вычислительной машины M, D проверит SD M и если круглая, отметит ее «u», а если круглая, отметит ее «s».
20 H — вычислительная машина. H вычисляет B', поддерживает R и N. H содержит D и U и неопределенную машину (или процесс), которая поддерживает N и R и предоставляет D эквивалентное SD N. E также вычисляет фигуры B' и собирает фигуры B'.
21 R — запись или подсчет количества успешных (без кружков) SD, протестированных D
22 N — число, начинающееся с 1, которое должно быть преобразовано в SD машиной E. E сохраняет N.
23 K — число. DN H.
5 m-конфигурация — идентификатор инструкции, либо символ в таблице инструкций, либо строка символов, представляющая номер инструкции на ленте универсальной машины (например, «DAAAAA = инструкция № 5»). В SD Тьюринга m-конфигурация появляется дважды в каждой инструкции, самая левая строка — «текущая инструкция», самая правая строка — следующая инструкция.
24 полная конфигурация — номер (цифра 1 или 0 ) сканируемого квадрата, полная последовательность всех символов на ленте и m-конфигурация (идентификатор инструкции, либо символ, либо строка символов, представляющая число, например, «инструкция DAAAA = #5»)
25 RSi(x, y) — «в полной конфигурации x матрицы M символ в квадрате y — Si; «полная конфигурация» — определение №5
26 I(x, y) — «в полной конфигурации x матрицы M квадрат y сканируется»
27 Kqm(x) — «в полной конфигурации x машины M машинная конфигурация (номер инструкции) равна qm»
28 F(x,y) — «y является непосредственным последователем x» (следует за использованием Гёделем «f» в качестве функции-последователя).
29 G(x,y) — «x предшествует y», не обязательно сразу
30 Inst{qi, Sj Sk L ql} — это сокращение, как и Inst{qi, Sj Sk R ql} и Inst{qi, Sj Sk N ql} . См. ниже.
Тьюринг сокращает свой набор инструкций до трех «канонических форм» — одна для левого, правого и отсутствия движения. Si и Sk — символы на ленте.
Например, операции в первой строке: PSk = ПЕЧАТЬ символа Sk из набора A, C, D, 0, 1, u, v, w, x, y, z, : , затем переместить ленту ВЛЕВО.
Далее он сократил их до: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm
В Доказательстве №3 он называет первый из них «Inst{qi Sj Sk L ql}» и показывает, как записать всю машину SD в виде логической конъюнкции (логического ИЛИ): эта строка называется «Des(M)», как в «Description-of-M». То есть, если машина печатает 0, затем 1 и 0 на чередующихся квадратах вправо и так до бесконечности, она может иметь следующую таблицу (похожий пример приведен на странице 119):
q1, пусто, P0, R, q2
q2, пусто, P-пусто, R, q3
q3, пусто, P1, R, q4
q4, пусто, P-пусто, R, q1
(Это было приведено к канонической форме с инструкциями «p-blank», поэтому это немного отличается от примера Тьюринга.) Если поместить их в «форму Inst()», то инструкции будут следующими (помним: S0 пусто, S1 = 0, S2 = 1):
Инст {q1 S0 S1 R q2}
Инст {q2 S0 S0 R q3}
Инст {q3 S0 S2 R q4}
Инст {q4 S0 S0 R q1}
Сокращение до стандартного описания (SD) составит:
; ДАДДКРДАА ; ДААДДРДААА ; ДАААДДККРДАААА ; ДААААДДРДА ;
Это согласуется с его примером в книге (между каждой буквой и цифрой будет пробел). Универсальная машина U использует альтернативные пустые квадраты как места для размещения «указателей».