Доказательство поворотов - Turings proof - Wikipedia

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

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

Парадокс ричарда

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

Краткое определение Парадокс ричарда находится у Уайтхеда и Рассела Principia Mathematica:

Парадокс Ричарда заключается в следующем. Рассмотрим все десятичные числа, которые можно определить с помощью конечного числа слов; пусть E - класс таких десятичных знаков. Тогда E имеет

{ displaystyle aleph _ {0}}

термины; следовательно, его члены могут быть упорядочены как 1-й, 2-й, 3-й, ... Пусть N будет числом, определенным следующим образом [Уайтхед и Рассел теперь используют Диагональный метод Кантора ]; если n-я цифра в n-м десятичном знаке равна p, пусть n-я цифра в N будет p + 1 (или 0, если p = 9). Тогда N отличается от всех членов E, так как какое бы конечное значение n ни было, n-я цифра в N отличается от n-й цифры в n-м десятичном значении, составляющем E, и, следовательно, N отличается от n-го десятичного знака. Тем не менее, мы определили N конечным числом слов [т.е. это самое слово-определение чуть выше!] и, следовательно, N должен быть членом E. Таким образом, N одновременно является и не является членом E (Principia Mathematica, 2-е издание 1927 г., стр. 61).

Осложнения

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

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

Исправления Бернейса можно найти в НеразрешимыйС. 152–154; оригинал находится как:

"О вычислимых числах в приложении к Entscheidungsproblem. Поправка", Труды Лондонского математического общества (2), 43 (1936–37), 544-546.

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

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

Возникают и другие проблемы: в его Приложение Сообщение косвенно прокомментировало сложность статьи и прямо ее "наброски" (Сообщение в Неразрешимый, п. 299) и «интуитивная форма» доказательств (там же.). Пост должен был сделать следующие выводы:

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

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

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

Резюме доказательств

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

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

Второе доказательство: Этот, возможно, более знаком читателям как Теорема Райса: "Далее мы можем показать, что не может быть машины E, которая при поставке с S.D ["программой"] произвольной машины M будет определять, печатает ли M когда-либо данный символ (например, 0)"(его курсив, Неразрешимый, п. 134).

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

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

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

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

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

Резюме первого доказательства

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

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

Машина Тьюринга H пытается напечатать диагональное число нулей и единиц.

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

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

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

Тьюринг ранее продемонстрировал в своем комментарии, что все "вычислительные машины" - машины, которые вечно вычисляют числа как единицы и нули - могут быть записаны как S.D на ленте «универсальной машины» U. Большая часть его работы, ведущей к его первому доказательству, посвящена демонстрации того, что универсальная машина действительно существует, т.е.

Действительно существует универсальная машина U

Для каждого числа N действительно существует уникальный S.D,

Каждая машина Тьюринга имеет S.D.

Каждый S.D на ленте U может быть «запущен» U и будет производить такой же «вывод» (рис. 1, 0), что и исходная машина.

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

Затем Тьюринг описывает (довольно вольно) алгоритм (метод), которому должна следовать машина, которую он называет H. Машина H содержит в себе машину принятия решений D (таким образом, D является «подпрограммой» H). Алгоритм машины H выражен в таблице инструкций H или, возможно, в стандартном описании H на ленте и объединен с универсальной машиной U; Тьюринг этого не уточняет.

В ходе описания универсальной машины U Тьюринг продемонстрировал, что S.D машины (строка букв, похожая на «программу») может быть преобразована в целое число (с основанием 8) и наоборот. Любое число N (с основанием 8) можно преобразовать в S.D с помощью следующих замен: 1 на A, 2 на C, 3 на D, 4 на L, 5 на R, 6 на N, 7 на точку с запятой ";".

Как оказалось, уникальный номер машины H (D.N) - это число «K». Мы можем сделать вывод, что K - очень длинное число, возможно, состоящее из десятков тысяч цифр. Но это не важно для дальнейшего.

Машина H отвечает за преобразование любой число N в эквивалентную строку символов S.D для проверки подмашины D. (На языке программирования: H передает произвольное «SD» в D, а D возвращает «удовлетворительно» или «неудовлетворительно».) Машина H также отвечает за ведение подсчета R («Запись»?) Успешных чисел (мы предполагаем, что количество «успешных» SD, т. е. R, намного меньше количества протестированных SD, т.е. N. Наконец, H печатает на участке своей ленты диагональное число «с бета-штрихом» B '. H создает эту B 'путем «моделирования» (в компьютерном смысле) «движений» каждой «удовлетворительной» машины / числа; в конечном итоге эта машина / тестируемое число придет к своей R-й «цифре» (1 или 0), и H напечатает его. Затем H отвечает за «очистку беспорядка», оставленного симуляцией, увеличивает N и продолжает свои тесты, до бесконечности.

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

Пример для иллюстрации первого доказательства

Пример: предположим, что машина H проверила 13472 числа и выдала 5 удовлетворительных чисел, то есть H преобразовал числа от 1 до 13472 в S.D (строки символов) и передал их D для проверки. Как следствие, H подсчитал 5 удовлетворительных чисел и провел первое из них до своей 1-й «цифры», второе - до 2-го, третье - до 3-го, четвертое - до 4-го, а пятое - до 5-го. Теперь счетчик равен N = 13472, R = 5 и B '= ".10011" (например). 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 ... 3214, и это число неудачно. Затем H увеличивает N, чтобы получить K = 4355 ... 3215, т.е. собственный номер. H преобразовывает это в «LDDR ... DCAR» и передает его машине принятия решений D. Машина принятия решений D должна вернуть «удовлетворительно» (то есть: H должна по определению продолжай и продолжай тестирование, до бесконечности, потому что он «без круга»). Итак, H теперь увеличивает счет R с 12 до 13, а затем повторно преобразует проверяемое число K в его S.D и использует U для его моделирования. Но это означает, что H будет моделировать свои собственные движения. Что будет делать симуляция в первую очередь? Эта симуляция K-aka-H либо создает новый N, либо «сбрасывает» «старый» N на 1. Этот «K-aka-H» либо создает новый R, либо «сбрасывает» «старый» R на 0. Старый. -H «запускает» новый «K-aka-H», пока не достигнет своей 12-й цифры.

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

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

Резюме второго доказательства

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

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

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

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

Детали второго доказательства

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

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

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

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

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

BBBBB .... BBBB ... до бесконечности

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

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

Предполагать M печатает этот узор:

M => ... AB01AB0010AB…

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

M1 = ... AB01AB0010AB ...

M2 = ... AB01AB0010AB ...

M3 = ... AB01AB0010AB ...

M4 = ... AB01AB0010AB ...

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

Теперь Тьюринг объединяет машины 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 выводить единицы и нули. до бесконечности. Таким образом, у нас есть метод определения того, не содержит ли M окружности. По доказательству 1 это невозможно. Итак, первое утверждение, что E существует, неверно: E не существует.

Резюме третьего доказательства

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

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

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

«Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы» (Franzén, p. 67)

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

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

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

Детали третьего доказательства

[Если читатели намерены подробно изучить доказательство, они должны исправить свои копии страниц третьего доказательства с исправлениями, внесенными Тьюрингом. Читатели также должны иметь солидный фон в (i) логике (ii) статье Курт Гёдель: "О формально неразрешимых предложениях Principia Mathematica и родственных систем "(перепечатано в Неразрешимый, п. 5). Для получения помощи с бумагой Гёделя им следует обратиться, например, к Эрнест Нагель и Джеймс Р. Ньюман, Доказательство Гёделя, 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) «Машинный код» M состоит только из нескольких букв и точки с запятой, т.е. 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песок 0s вечно движется вправо.

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

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

(vi) Тьюринг сократил огромное возможное количество инструкций в «M-коде» (опять же: код M, который должен появиться на ленте) до небольшого канонического набора, одного из трех, подобных этому: {qi Sj Sk R ql} например Если машина выполняет инструкцию #qi и символ Sj находится на сканируемом квадрате, то напечатайте символ Sk и перейдите вправо, а затем перейдите к инструкции ql.: Остальные инструкции аналогичны, кодируются для "Left" L и "No motion" N. Именно этот набор кодируется строкой символов qi = DA ... A, Sj = DC ... C, Sk = DC ... C, R, ql = DA .... A. Каждая инструкция отделяется от другой точкой с запятой. Например, {q5, S1 S0 L q3} означает: Инструкция №5: Если отсканированный символ 0 затем распечатайте пустой, перейдите влево, затем перейдите к инструкции №3. Он кодируется следующим образом

; D A A A A A D C D L D A A A

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

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

(Eu) N (u) & (x) (... и т. Д ...) (Неразрешимый, п. 146)

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

Что это значит для доказательства? Первая подсказка означает, что простое изучение М-кода на ленте не покажет, 0 всегда печатается U + "M-кодом". Испытательная машина может искать появление ОКРУГ КОЛУМБИЯ в одной из строк символов, представляющих инструкцию. Но будет ли эта инструкция когда-нибудь «выполнена»? Что-то должно «запустить код», чтобы узнать. Это может быть машина или строки в формальном доказательстве, то есть в лемме №1.

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

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

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

«Множество E вычислимо разрешимо тогда и только тогда, когда и E, и его дополнение вычислимо перечислимы» (Franzén, p. 67)

Процитирую Францена:

"Предложение A называется разрешимым в формальная система S, если A или его отрицание доказуемо в S »(Franzén, p. 65)

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

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

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

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

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

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

Пример для иллюстрации третьего доказательства

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

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

R, RIGHT: посмотрите направо и переместите ленту влево или переместите головку ленты вправо

L, ВЛЕВО: посмотрите влево и переместите ленту вправо или переместите головку ленты влево

E, УДАЛИТЬ отсканированный квадрат (например, сделать квадрат пустым)

P0 ,: PRINT 0 в отсканированном квадрате

P1 ,: ПЕЧАТЬ 1 в отсканированном квадрате

Jb_n, JUMP-IF-blank-to-command_ # n,

J0_n, JUMP-IF-0-к-инструкции_ # n,

J1_n, JUMP-IF-1-to-Instrucntion_ # n,

HALT.

В случаях 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) R,

config # 2: 1 (б) P1,

конфигурация # 3: 1 (1) R,

конфигурация # 4: 11 (б) P1,

конфигурация # 5: 11 (1) H

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

начало: P1, R, P1, R, P1, P0, L, J1_7, H

(б) bb P1,

(1) bb R,

1 (б) б P1,

1 (1) б R,

11 (б) П1,

11 (1) P0,

11 (0) л,

1 (1) 0 J1_7

1 (1) 0 л

(1) 10 J0_7

(1) 10 л

(б) 110 J0_7

(б) 110 H

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

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

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

Глоссарий терминов, используемых Тьюрингом

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

2 M - машина с конечной таблицей команд и сканирующей / печатающей головкой. M перемещает бесконечную ленту, разделенную на квадраты, каждый из которых «способен нести символ». Машинные инструкции только следующие: переместите один квадрат влево, переместите один квадрат вправо, на отсканированном квадрате напечатайте символ p, сотрите отсканированный квадрат, если символ p, то выполните команду aaa, если отсканированный символ не p, то команда do aaa, если отсканированный символ отсутствует, выполните команду aaa, если отсканированный символ является любой инструкцией do aaa [где «aaa» - идентификатор инструкции].

3 вычислительная машина - M, который печатает символы двух типов, символы первого типа называются «цифрами» и представляют собой только двоичные символы 1 и 0; символы второго типа - любые другие символы.

4 цифры - символы 1 и 0, он же «символы первого рода»

5 м-конфигурация - идентификатор команды, либо символ в таблице команд, либо строка символов, представляющая номер команды на ленте универсальной машины (например, «DAAAAA = # 5»)

6 символы второго рода - любые символы кроме 1 и 0

7 круговой - неудачная вычислительная машина. Он не может напечатать, до бесконечности, цифры 0 или же 1 которые представляют в двоичном формате число, которое он вычисляет

8 без круга - успешная вычислительная машина. Он печатает, до бесконечности, цифры 0 или же 1 которые представляют в двоичном формате число, которое он вычисляет

9 последовательность - как в «последовательности, вычисленной автоматом»: символы первого типа, также известные как цифры, или символы 0 и 1.

10 вычислимая последовательность - можно вычислить на машине без круга

11 S.D - Стандартное описание: последовательность символов A, C, D, L, R, N, «;» на ленте машины Тьюринга

12 D.N - Номер описания: S.D преобразован в число: 1 = A, 2 = C, 3 = D, 4 = L, 5 = R, 6 = N, 7 =;

13 М (п) - машина, D.N которой является числом «n»

14 удовлетворительно - S.D или D.N, обозначающие машину без круга

15 U - машина с «универсальной» таблицей инструкций. Если U «снабжен лентой, в начале которой написано S.D некоторой вычислительной машины M, U вычислит ту же последовательность, что и M.»

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

17 ты - неудовлетворительный, т.е. циркулярный, С.Д.

18 s - удовлетворительная, т. Е. Без круга С.Д.

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

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

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

22 N - число, начинающееся с 1, которое будет преобразовано в S.D машиной E. E поддерживает N.

23 K - число. D.N. H.

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

5 м-конфигурация - идентификатор инструкции, либо символ в таблице инструкций, либо строка символов, представляющая номер инструкции на ленте универсальной машины (например, «DAAAAA = инструкция # 5»). В S.D Тьюринга m-конфигурация появляется дважды в каждой инструкции, самая левая строка - это «текущая инструкция»; самая правая строка - это следующая инструкция.

24 полная конфигурация - номер (цифра 1 или же 0) сканированного квадрата, полную последовательность всех символов на ленте и m-конфигурацию (идентификатор инструкции, либо символ, либо строка символов, представляющих число, например, «инструкция DAAAA = # 5»)

25 RSi (х, у) - «в полной конфигурации x из M символ на квадрате y - Si;« полная конфигурация »- это определение №5

26 Я (х, у) - «в полной конфигурации x of M сканируется квадрат y»

27 Ккм (х) - «в полной конфигурации x of M конфигурация машины (номер инструкции) равна qm»

28 F (х, у) - "y - это немедленный преемник x »(следует за использованием Гёделем« f »в качестве функции-преемника).

29 G (х, у) - «x предшествует y», не обязательно сразу

30 Inst {qi, Sj Sk L ql} это аббревиатура, как и Inst {qi, Sj Sk R ql}, и Inst {qi, Sj Sk N ql}. Смотри ниже.

Тьюринг сокращает свой набор инструкций до трех «канонических форм» - для левого, правого и запретного движения. Si и Sk - символы на ленте.

лента Финал

m-config Операции с символами m-config

qi Si PSk, L qm

qi Si PSk, R qm

qi Si PSk, Н · м

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

q1, пробел, P0, R, q2

q2, пустой, P-blank, R, q3

q3, пустой, P1, R, q4

q4, пустой, P-пустой, R, q1

(Это было приведено к канонической форме с помощью инструкций «p-blank», поэтому он немного отличается от примера Тьюринга.) Если поместить их в «форму Inst ()», инструкции будут следующими (помня: S0 пусто, S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2}

Inst {q2 S0 S0 R q3}

Inst {q3 S0 S2 R q4}

Inst {q4 S0 S0 R q1}

Сокращение до Стандартного описания (S.D) будет:

; Д А Д Д З Р Д А А; Д А А Д Д Р Д А А А; Д А А А Д Д З Р Д А А А А; Д А А А А Д Д Р Д А;

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