Доказательство Тьюринга

Доказательство Тьюринга — это доказательство Алана Тьюринга , впервые опубликованное в ноябре 1936 года. под названием « О вычислимых числах с применением к проблеме Entscheidungs ». Это было второе доказательство (после теоремы Чёрча ) отрицания проблемы Гильберта Entscheidungs ; то есть гипотеза о том, что на некоторые чисто математические вопросы типа «да-нет» невозможно ответить с помощью вычислений; более технически, некоторые проблемы решения являются « неразрешимыми » в том смысле, что не существует единого алгоритма, который безошибочно дает правильный ответ «да» или «нет» для каждого случая проблемы. По словам Тьюринга:«То, что я докажу, сильно отличается от хорошо известных результатов Гёделя… Теперь я покажу, что не существует общего метода, который бы определял, ли данная формула U доказуема в K [ Principia Mathematica ]».

Тьюринг последовал этому доказательству вместе с двумя другими. И второе, и третье опираются на первое. Все полагаются на его разработку «вычислительных машин», похожих на пишущие машинки, которые подчиняются простому набору правил, и его последующую разработку «универсальной вычислительной машины».

доказательств

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

Первое доказательство : не существует «вычислительной машины», которая могла бы решить, является ли произвольная «вычислительная машина» (представленная целым числом 1, 2, 3,...) «свободной от кругов» (т. е. продолжает ли она печатать свои число в двоичном формате до бесконечности): «...у нас нет общего процесса, позволяющего сделать это за конечное число шагов» (с. 132, там же ). Доказательство Тьюринга, хотя и использует «диагональный процесс», на самом деле показывает, что его машина (называемая H) не может вычислить свое собственное число, не говоря уже о всем диагональном числе ( диагональный аргумент Кантора ): «Ошибка в аргументе заключается в том, что предположение, что B [диагональное число] вычислимо» Доказательство не требует много математики.

Второе доказательство : Возможно, оно более знакомо читателям как теорема Райса : «Мы можем показать дальше, что не может быть машины Е, которая, будучи снабжена SD ["программой"] произвольной машины М, будет определять, будет ли М когда-либо печатает заданный символ (скажем, 0) "

Третье доказательство : «Для каждой вычислительной машины М мы строим формулу Un(M) и показываем, что если существует общий метод определения того, доказуема ли Un(M), то существует и общий метод определения того, является ли M когда-либо печатает 0".

Третье доказательство требует использования формальной логики для доказательства первой леммы, за которой следует краткое словесное доказательство второй:

Лемма 1: Если S1 [символ «0»] появляется на ленте в некоторой полной конфигурации M, то Un(M) доказуемо.
Лемма 2: [Обратное] Если Un(M) доказуемо, то S1 [символ «0»] появляется на ленте в некоторой полной конфигурации M.

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

первого

Тьюринг создал множество сокращений. Определения см. в глоссарии в конце статьи.

Некоторые ключевые разъяснения:

Машина Тьюринга H пытается напечатать диагональное число из 0 и 1.
Это диагональное число создается, когда H фактически «моделирует» каждую оцениваемую «успешную» машину и печатает R-ю «цифру» (1 или 0) R-й «успешной» машины.

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

Тьюринг начинает доказательство с утверждения о существовании машины «решения/определения» D. При передаче любого SD (строка символов A, C, D, L, R, N, точка с запятой «;») она определит, является ли это SD (строка символов) представляет собой «вычислительную машину», которая либо «круглая» — и, следовательно, «неудовлетворительная u» — либо «без кругов» — и, следовательно, «удовлетворительная s».

Ранее Тьюринг продемонстрировал в своем комментарии, что все «вычислительные машины — машины, которые вечно вычисляют числа как 1 и 0 — могут быть записаны как SD на ленте «универсальной машины» U. Большая часть его работ, предшествовавших его первой доказательство тратится на демонстрацию того, что универсальная машина действительно существует, т.е.
Действительно существует универсальная машина U
Для каждого числа N действительно существует уникальное СО,
Каждая машина Тьюринга имеет 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 («Запись»?) успешных чисел (мы предполагаем, что число «успешных» SD, т. е. R, намного меньше числа протестированных SD, т. е. N). Наконец, H печатает на участке своей ленты диагональное число, «бета-штрихованное» B', создает это B. ' путем «моделирования» (в компьютерном смысле) «движений» каждой «удовлетворительной» машины/числа; в конечном итоге эта испытуемая машина/число достигнет своей R-й «цифры» (1 или 0), и H напечатает затем он отвечает за «уборку беспорядка», оставленного симуляцией, увеличивая N и продолжая тесты до бесконечности .

Примечание. Все эти машины, за которыми охотится Х, — это то, что Тьюринг назвал «вычислительными машинами». Они вычисляют двоично-десятичные числа в бесконечном потоке того, что Тьюринг называл «цифрами»: только символы 1 и 0.

иллюстрирующий первое

Пример: предположим, что машина H проверила 13472 числа и выдала 5 удовлетворительных чисел, т.е. H преобразовала числа от 1 до 13472 в SD (строки символов) и передала их D для проверки. В результате H подсчитал 5 удовлетворительных чисел и прогнал первое до его 1-й «цифры», второе — до 2-й цифры, третье — до 3-й цифры, четвертое — до 4-й цифры и пятое — до 5-й цифры. Теперь счетчик составляет N = 13472, R = 5 и B' = «.10011» (например). H убирает беспорядок на своей ленте и продолжает:

H увеличивает N = 13473 и преобразует «13473» в строку символов ADRLD. Если субмашина D считает ADLRD неудовлетворительной, то H оставляет счетную запись R равной 5. H увеличит число N до 13474 и продолжит работу дальше. С другой стороны, если D сочтет ADLRD удовлетворительным, то H увеличит R до 6. H преобразует N (снова) в ADLRD [это всего лишь пример, ADLRD, вероятно, бесполезен] и «запустит» его с помощью универсальной машины U до тех пор, пока эта тестируемая машина (U «работает» ADRLD) печатает свою шестую «цифру», т. е. 1 или 0. H напечатает это шестое число (например, «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. Старый -H «запускает» новый «K-aka-H», пока он не достигнет своей 12-й цифры.

Но до 13-й цифры он так и не доходит; K-aka-H в конечном итоге снова достигает 4355...321 5 , и K-aka-H должен повторить тест. К-ака-Н никогда не достигнет 13-й цифры. H-машина, вероятно, просто печатает свои копии до бесконечности на чистой ленте. Но это противоречит предпосылке, что H является удовлетворительной некруговой вычислительной машиной, которая постоянно печатает 1 и 0 диагональных чисел. (Мы увидим то же самое, если N сбросить на 1, а R сбросить на 0.)

Если читатель в это не верит, он может написать «заглушку» для машины принятия решений D (заглушка «D» вернет «удовлетворительно»), а затем увидеть своими глазами, что происходит в тот момент, когда машина H встречает свой собственный номер.

второго

В книге меньше одной страницы, переход от предпосылок к заключению неясен.

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

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

1. Если машина E существует, то существует машина G, которая определяет, печатает ли M 0 бесконечно часто, И
2. Если E существует, то существует другой процесс (мы можем назвать процесс/машину G' для справки), который определяет, печатает ли M 1 бесконечно часто, ПОЭТОМУ
3. Когда мы объединяем G с G', у нас есть процесс, который определяет, печатает ли M бесконечное число цифр, И
4. ЕСЛИ процесс «G с G'» определяет, что M печатает бесконечность фигур, ТО «G с G'» определил, что M свободен от кругов, НО
5. Этот процесс «G с G'», определяющий, является ли M свободным от кругов, согласно доказательству 1, не может существовать, ПОЭТОМУ
6. Машины Е не существует.

Подробности

Трудность доказательства заключается в шаге 1. Читателю будет полезно понять, что Тьюринг не объясняет свою тонкую работу. (В двух словах: он использует определенные эквиваленты между «экзистенциальными» и «универсальными операторами» вместе с их эквивалентными выражениями, записанными с помощью логических операторов.)

Вот пример: предположим, мы видим перед собой парковку, полную сотен автомобилей. Решаем обойти весь участок в поисках: «Машины со спущенными (плохими) шинами». Примерно через час мы нашли две «машины с плохими шинами». Теперь мы можем с уверенностью сказать: «У некоторых автомобилей плохие шины». Или мы могли бы сказать: «Неправда, что «У всех машин хорошие шины»». Или: «Это правда: «не у всех машин хорошие шины». Перейдем к другому лоту. Здесь мы обнаруживаем, что «у всех машин хорошие шины». Мы могли бы сказать: «Нет ни одного случая, чтобы у автомобиля была неисправная шина». Таким образом, мы видим, что если мы можем сказать что-то о каждой машине в отдельности, то мы можем сказать что-то и о ВСЕХ вместе взятых.

Вот что делает Тьюринг:Из M он создает набор машин { M 1, M 2, M 3, M 4, ..., Mn } и о каждой пишет предложение: « X печатает хотя бы один 0» и допускает только два « значения истинности ». », True = пусто или False = :0:. Одно за другим он определяет истинность предложения для каждой машины и составляет строку из пробелов или :0: или некоторой их комбинации. Мы могли бы получить что-то вроде этого: « M 1 печатает 0» = Истина И « M 2 печатает 0» = Истина И « M 3 печатает 0» = Истина И « M 4 печатает 0» = Ложь, ... И « Mn печатает 0» = Ложь. Он получает строку

BBB:0::0::0: ... :0: ... до бесконечности

если существует бесконечное число машин Mn . С другой стороны, если бы каждая машина выдавала «Истина», тогда выражение на ленте было бы таким:

ББББ....ББББ... до бесконечности

Таким образом, Тьюринг преобразовал утверждения о каждой машине, рассматриваемой отдельно, в одно «утверждение» (строку) обо всех из них. Учитывая машину (он называет ее G), которая создала это выражение, он может проверить его на своей машине E и определить, выдает ли она когда-либо 0. В нашем первом примере выше мы видим, что это действительно так, поэтому мы знаем, что не все M в нашей последовательности выводят 0. Но второй пример показывает, что, поскольку строка пуста, каждый Mn в нашей последовательности дает 0.

Все, что остается сделать Тьюрингу, — это создать процесс создания последовательности Mn из одного M.

Предположим, M печатает этот шаблон:

М => ...AB01AB0010AB…

Тьюринг создает еще одну машину F, которая берет M и обрабатывает последовательность Mn, которая последовательно преобразует первые n нулей в «0-бар» ( 0 ):

Он заявляет, не раскрывая подробностей, что эту машину F действительно можно собрать. Мы видим, что может произойти одно из нескольких событий. В F могут закончиться машины с нулями, или ему, возможно, придется продолжать до бесконечности, создавая машины для «отмены нулей».

Теперь Тьюринг объединяет машины E и F в составную машину G. G начинает с исходной M, затем использует F для создания всех машин-преемников M1, M2. . ., Мн. Затем 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 не существует.

третьего

Здесь Тьюринг доказывает, что «проблема Гильберта Entscheidungs ​​не может иметь решения». Вот он

…показать(-ют), что не может быть общего процесса определения того, доказуема ли данная формула U функционального исчисления K. ( там же ).

Обе леммы №1 и №2 необходимы для формирования необходимого «ЕСЛИ И ТОЛЬКО ЕСЛИ» (т.е. логической эквивалентности ), требуемого доказательством:

Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы (Францен, стр. 67).

Тьюринг демонстрирует существование формулы Un (M), которая, по сути, говорит, что «в некоторой полной конфигурации M 0 на ленте появляется » (стр. 146). Эта формула ИСТИННА, то есть она «конструктивна», и он показывает, как это сделать.

Затем Тьюринг доказывает две леммы, первая из которых требует всей тяжелой работы. (Второй вариант является обратным первому.) Затем он использует доведение до абсурда, чтобы доказать свой окончательный результат:

1. Существует формула Un (M). Эта формула ВЕРНА, И
2. Если проблема Entscheidungsproblem может быть решена, ТОГДА существует механический процесс определения того, является ли Un (M) доказуемым (выводимым), И
3. По леммам 1 и 2: Un (M) доказуемо ЕСЛИ И ТОЛЬКО ЕСЛИ 0 появляется в некоторой «полной конфигурации» M, И
4. ЕСЛИ 0 появляется в некоторой «полной конфигурации» M, ТО существует механический процесс, который определит, печатает ли когда-либо произвольный M 0 , И
5. По доказательству 2 не существует механического процесса, который бы определял, печатает ли когда-либо произвольный M 0 , ПОЭТОМУ
6. Un (M) недоказуемо ( это ИСТИНА, но не доказуемо ), что означает, что проблема Entscheidungsproblem неразрешима.

третьего

[Если читатели намерены подробно изучить доказательство, им следует исправить свои копии страниц третьего доказательства с исправлениями, предоставленными Тьюрингом. Читатели также должны иметь солидный опыт в (i) логике, (ii) статье Курта Гёделя : « О формально неразрешимых утверждениях Principia Mathematica и родственных системах ». За помощью в работе Гёделя они могут обратиться, например, к Эрнесту Нагелю и Джеймсу Р. Ньюману , Gödel's Proof , New York University Press, 1958.]

Чтобы разобраться в технических деталях, читателю необходимо понимать определение слова «доказуемый» и знать важные «подсказки».

«Доказуемость» означает, в смысле Гёделя, что (i) сама система аксиом достаточно мощна, чтобы произвести (выразить) предложение «Это предложение доказуемо», и (ii) что в любом произвольном «хорошо построенном» доказательстве символы приводят аксиомы, определения и замены к символам заключения.

Первая подсказка: «Поместим описание М в первую стандартную форму §6». В разделе 6 описывается очень специфическое «кодирование» машины M на ленте «универсальной машины» U. Это требует от читателя знания некоторых особенностей универсальной машины U Тьюринга и схемы кодирования.

(i) Универсальная машина представляет собой набор «универсальных» инструкций, которые хранятся в «таблице инструкций». Отдельно от этого на ленте U «вычислительная машина» M будет находиться как «M-код». Универсальная таблица инструкций позволяет печатать на ленте символы A, C, D, 0, 1, u, v, w, x, y, z, : . Различные машины M могут печатать эти символы только косвенно, давая команду U напечатать их.

(ii) «Машинный код» М состоит всего из нескольких букв и точки с запятой, т.е. D, C, A, R, L, N, ; . Нигде в «коде» М не появятся числовые «цифры» (символы) 1 и 0 . Если M хочет, чтобы U напечатал символ из бланка коллекции, 0, 1 , тогда он использует один из следующих кодов, чтобы сообщить U о необходимости их печати. Чтобы еще больше запутать ситуацию, Тьюринг называет эти символы S0, S1 и S2, т.е.

пусто = S0 = D

0 = S1 = постоянный ток

1 = S2 = DCC

(iii) «Вычислительная машина», независимо от того, встроена ли она непосредственно в таблицу (как показывают его первые примеры) или в виде машинного кода M на ленте универсальной машины U, печатает свой номер на пустой ленте (справа от M). -код, если он есть) как 1 с и 0 с, всегда идущие вправо.

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

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

(vi) Тьюринг свел огромное возможное количество инструкций в «М-коде» (опять же: код М, который должен появиться на ленте) к небольшому каноническому набору, одному из трех подобных этому: {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. Он кодируется следующим образом

; ДАААААDCDLDAAA

Вторая подсказка: Тьюринг использует идеи, представленные в статье Гёделя, то есть «геделизацию» (по крайней мере части) формулы для Un (M). Эта подсказка появляется только в виде сноски на странице 138 ( Дэвис (1965) , стр. 138): «Последовательность r простых чисел обозначается ^ (r)» ( там же ). [Здесь r внутри круглых скобок «приподнято». ] Эта «последовательность простых чисел» появляется в формуле под названием F^(n).

Третья подсказка: Это усиливает вторую подсказку. В оригинальной попытке Тьюринга доказательства используется выражение:

(Eu)N(u) & (x)(... и т.д. ...)

Ранее в статье Тьюринг уже использовал это выражение (стр. 138) и определил N(u) как «u — неотрицательное целое число» ( там же ) (т.е. число Гёделя). Но с поправками Бернейса Тьюринг отказался от этого подхода (т.е. от использования N(u)) и единственное место, где «число Гёделя» появляется явно, — это то, где он использует F^(n).

Что это значит для доказательства? Первая подсказка означает, что простое изучение М-кода на ленте не покажет, был ли когда-либо напечатан символ 0 с помощью U+ «М-кода». Тестирующая машина может искать появление DC в одной из строк символов, представляющих инструкцию. Но будет ли эта инструкция когда-нибудь «выполнена»? Чтобы выяснить это, нужно что-то «запустить код». Это что-то может быть машиной, а может быть строками в формальном доказательстве, т.е. лемме №1.

Вторая и третья подсказки означают, что, поскольку в основе лежит статья Гёделя, доказательство затруднено.

В приведенном ниже примере мы на самом деле сконструируем простую «теорему» — небольшую машинную программу Пост-Тьюринга, которая «запустит ее». Мы увидим, насколько механической может быть правильно сформулированная теорема. Доказательство, как мы увидим, — это всего лишь «проверка» теоремы, которую мы проводим, вставляя «пример доказательства» в начало и наблюдая, что получится в конце.

Обе леммы №1 и №2 необходимы для формирования необходимого «ЕСЛИ И ТОЛЬКО ЕСЛИ» (т.е. логической эквивалентности), требуемого доказательством:

Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы. (Францен, стр. 67)

Цитирую Франзена:

Предложение A называется разрешимым в формальной системе S, если либо A, либо его отрицание доказуемо в S. (Францен, стр. 65).

Ранее в своей книге Франзен дал определение понятию «доказуемое»:

Формальная система — это система аксиом (выраженных на некотором формально определенном языке) и правил рассуждения (также называемых правилами вывода), используемых для вывода теорем системы. Теорема — это любое утверждение на языке системы, которое можно получить путем применения правил рассуждения, начиная с аксиом. Доказательство — это конечная последовательность таких применений, ведущая к теореме в качестве своего заключения. ( там же, стр. 17)

Таким образом, «предложение» — это строка символов, а теорема — это строка символов.

Тьюринг сталкивается со следующей задачей:

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

Таким образом, «строка предложений» будет строкой символов. Единственные разрешенные отдельные символы будут взяты из символов Гёделя, определенных в его статье. (В следующем примере мы используем «<» и «>» вокруг «цифры», чтобы указать, что «цифра» — это символ, сканируемый машиной. ).

третье

Далее мы должны напомнить себе, что каждая из «вычислительных машин» Тьюринга представляет собой генератор/создатель двоичных чисел, который начинает работу на «чистой ленте». Правильно сконструированный, он всегда работает до бесконечности, но его инструкции всегда конечны. В доказательствах Тьюринга лента Тьюринга имела «левый конец», но простиралась до бесконечности правым. В качестве примера ниже мы предположим, что «машина» — это не универсальная машина, а более простая «специальная машина» с инструкциями в таблице.

Наш пример основан на модифицированной модели машины Тьюринга Пост-Тьюринга . Эта модель печатает только символы 0 и 1. Считается, что на пустой ленте все символы b. Наша модифицированная модель требует от нас добавить еще две инструкции к семи инструкциям Пост-Тьюринга. Сокращения, которые мы будем использовать:

R, ВПРАВО: посмотрите направо и переместите ленту влево или переместите головку ленты вправо.
L, ВЛЕВО: посмотрите налево и переместите ленту вправо или переместите головку ленты влево.
E, СТЕРЕТЬ отсканированный квадрат (например, сделать квадрат пустым)
P0,: ПЕЧАТЬ 0 в отсканированном квадрате
P1: ПЕЧАТЬ 1 в отсканированном квадрате
Jb_n, JUMP-IF-пробел к инструкции_#n,
J0_n, JUMP-IF-0-to-instruction_#n,
J1_n, JUMP-IF-1-к инструкции_#n,
ОСТАНОВКА.

В случаях R, L, E, P0 и P1 после выполнения своей задачи машина переходит к следующей инструкции в числовой последовательности; то же самое касается прыжков, если их тесты провалятся.

Но для краткости в наших примерах будут использоваться только три квадрата. И они всегда будут начинаться с пробелов со отсканированным квадратом слева: т.е. bbb. С двумя символами 1, 0 и пробелом мы можем иметь 27 различных конфигураций:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

Здесь нужно быть осторожным, потому что вполне возможно, что алгоритм (временно) оставит пробелы между цифрами, а затем вернется и что-то заполнит. Более вероятно, что алгоритм может сделать это намеренно. Фактически, машина Тьюринга делает это — она печатает на чередующихся квадратах, оставляя пробелы между фигурами, чтобы можно было печатать символы локатора.

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

b(b)0 это означает: «Лента пуста слева от пустого места, но левое пустое «в игре», отсканированный квадрат пуст, «0», пробелы справа»
1(0)1 это означает: «Лента пуста слева, затем 1, отсканированный квадрат равен '0'»

Напишем простую программу:

начало: P1, R, P1, R, P1, H

Помните, что мы всегда начинаем с пустой ленты. Полная конфигурация печатает символы на ленте, после чего следует следующая инструкция:

запуск конфигурации: (б) P1,
конфигурация №1: (1) Р,
конфигурация №2: 1(б) П1,
конфигурация №3: 1(1) Р,
конфигурация №4: 11(б) П1,
конфигурация №5: 11(1) Ч

Добавим в формулу «скачок». Сделав это, мы поймем, почему полная конфигурация должна включать символы ленты. (На самом деле, мы видим это лучше ниже.) Эта небольшая программа печатает три «1» вправо, меняет направление и перемещается влево, печатая 0, пока не достигнет пробела. Мы напечатаем все символы, которые использует наша машина:

начало: P1, R, P1, R, P1, P0, L, J1_7, H
(б)bb P1,
(1)bb R,
1(б)б П1,
1(1)б Р,
11(б) П1,
11(1) П0,
11(0) Л,
1(1)0 J1_7
1(1)0 л
(1)10 Дж0_7
(1)10 л
(б)110 Дж0_7
(б) 110 Н

Здесь, в конце, мы обнаруживаем, что пробел слева «вступил в игру», поэтому мы оставляем его как часть общей конфигурации.

Учитывая, что мы правильно выполнили свою работу, добавляем стартовые условия и смотрим, «куда пойдет теорема». Полученная конфигурация — число 110 — является ДОКАЗАТЕЛЬСТВОМ.

• Первой задачей Тьюринга было написать обобщенное выражение, используя логические символы, чтобы точно выразить то, что будет делать его Un(M).
• Вторая задача Тьюринга — «геделизировать» эту чрезвычайно длинную строку символов, используя технику Гёделя, заключающуюся в присвоении простых чисел символам и возведении простых чисел в степени простых чисел, согласно методу Гёделя.

Осложнения

Доказательство Тьюринга осложняется большим количеством определений и смешивается с тем, что Мартин Дэвис назвал «мелкими техническими деталями» и «... техническими деталями, [которые] неверны в том виде, в котором они даны». Сам Тьюринг опубликовал «Поправку» в 1938 году: «Автор обязан П. Бернейсу за указание на эти ошибки».

В частности, третье доказательство в своей первоначальной форме сильно испорчено техническими ошибками. И даже после предложений Бернейса и исправлений Тьюринга в описании универсальной машины остались ошибки . И что сбивает с толку, поскольку Тьюринг не смог исправить свою оригинальную статью, некоторый текст в основной части статьи напоминает ошибочную первую попытку Тьюринга.

Исправления Бернейса можно найти у Дэвиса (1965) , стр. 152–154; оригинал можно найти как «О вычислимых числах с применением к Entscheidungsproblem. Исправление», Proceedings of the London Mathematical Society (2), 43 (1938), 544–546.

В онлайн-версии статьи Тьюринга эти исправления содержатся в приложении; однако поправки к Универсальной Машине следует найти в анализе, предоставленном Эмилем Постом .

Поначалу единственным математиком, который обратил пристальное внимание на детали доказательства, был Пост (ср. Ходжес, стр. 125) — главным образом потому, что он одновременно пришел к аналогичному сведению «алгоритма» к примитивным машиноподобным действиям, поэтому он лично интересовался доказательствами. Как ни странно (вероятно, вмешалась Вторая мировая война), Посту потребовалось около десяти лет, чтобы проанализировать это в приложении к своей статье «Рекурсивная неразрешимость проблемы Туэ» , 1947 год.

Возникают и другие проблемы: в своем приложении Пост косвенно прокомментировал сложность статьи и прямо ее «контурный характер». и «интуитивная форма» доказательств. Посту пришлось сделать несколько выводов:

Если наша критика верна, то говорят, что машина не имеет кругов, если она является вычислительной машиной Тьюринга... которая печатает бесконечное количество нулей и единиц. И две рассматриваемые теоремы Тьюринга на самом деле заключаются в следующем. Не существует машины Тьюринга... которая, если ей будет присвоено произвольное положительное целое число n, определит, является ли n DN вычислительной... машины Тьюринга, не имеющей кругов. [Во-вторых], не существует машины соглашения Тьюринга, которая при наличии произвольного положительного целого числа n будет определять, является ли n DN вычислительной машины Тьюринга... которая когда-либо печатает заданный символ (скажем, 0).

Любой, кто когда-либо пытался прочитать эту газету, поймет жалобу Ходжеса:

Статья начиналась привлекательно, но вскоре погрузилась (в типичной для Тьюринга манере) в дебри малоизвестной немецкой готики, чтобы разработать таблицу инструкций для универсальной машины. Последними, кто взглянет на это, будут прикладные математики, которым пришлось прибегнуть к практическим вычислениям... (Ходжес, стр. 124).

терминов,

1 вычислимое число — число, десятичная дробь которого может быть вычислена машиной (т. е. конечными средствами, такими как алгоритм)

2 М — машина с конечной таблицей команд и сканирующей/печатающей головкой. M перемещает бесконечную ленту, разделенную на квадраты, каждый из которых «способен нести символ». Машинные инструкции заключаются только в следующем: переместите один квадрат влево, переместите один квадрат вправо, на отсканированном квадрате напечатайте символ p, сотрите отсканированный квадрат, если это символ p, то выполните команду aaa, если отсканированный символ не p, то выполните инструкцию aaa, если отсканированный символ отсутствует, то выполните инструкцию aaa, если отсканированный символ является любой инструкцией do 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 «снабжен лентой, на начале которой записан SD некоторой вычислительной машины M, U вычислит ту же последовательность, что и M».

16 β' — «бета-штрих»: так называемое «диагональное число», состоящее из n-й цифры (т.е. 0 или 1) n-й вычислимой последовательности [также: вычислимое число H, см. ниже ]

17 ю — неудовлетворительная, т.е. круговая, СД

18 с — удовлетворительное, т.е. СД без кругов

19 D — машина, содержащаяся в H (см. ниже). При поставке с SD любой вычислительной машины M, D проверит SD M и, если круговой, пометит его буквой «u», а если круга нет, пометит его буквой «s».

20 Н — вычислительная машина. H вычисляет B', поддерживает R и N. H содержит D и U и неопределенную машину (или процесс), которая поддерживает N и R и предоставляет D эквивалентное SD для N. E также вычисляет цифры B' и собирает цифры из Б'.

21 R — запись или подсчет количества успешных (без кружков) SD, протестированных D.

22 N — число, начинающееся с 1, которое должно быть преобразовано в SD машиной E. E поддерживает N.

23 К — число. DN Х.

Требуется для доказательства № 3.

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)». , как в «Описании-М».т.е. если машина печатает 0, затем 1 и 0 в чередующихся квадратах вправо до бесконечности, она может иметь таблицу (аналогичный пример приведен на странице 119):

q1, пусто, P0, R, q2
q2, пробел, P-пробел, R, q3
q3, blank, 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 использует чередующиеся пустые квадраты в качестве мест для размещения «указателей».

Ссылки

Цитируемые работы

• Дэвис, Мартин (1965). Неразрешимые, основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Рэйвен Пресс. Две упомянутые выше статьи Поста включены в этот том. Другие статьи включают работы Гёделя, Чёрча, Россера и Клини.
  • Дэвис, Мартин (2004). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Дувр. ISBN  9780486432281 .
• Францен, Торкель (2005). Теорема Гёделя: неполное руководство по ее использованию и злоупотреблениям . АК Петерс.
• Ходжес, Эндрю (1983). Алан Тьюринг: Загадка . Нью-Йорк: Саймон и Шустер . См. Глава «Дух истины» содержит историю, ведущую к его доказательству, и обсуждение его.
• Райхенбах, Ганс (1947). Элементы символической логики . Нью-Йорк: Dover Publications, Inc.
• Тьюринг, AM (1937). «О вычислимых числах с применением к проблеме Entscheidungs». Труды Лондонского математического общества . 2. 42 (1): 230–65. дои : 10.1112/plms/s2-42.1.230 . S2CID   73712 .
• Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs. Исправление» . Труды Лондонского математического общества . 2. 43 (6): 544–6. дои : 10.1112/plms/s2-43.6.544 . Это эпохальная статья, в которой Тьюринг дает определение машинам Тьюринга и показывает, что проблема Entscheidungs ​​неразрешима.