Машина Тьюринга

Классы автоматов

(При нажатии на каждый слой открывается статья на эту тему)

Машина Тьюринга представляет собой математическую модель вычислений , которая определяет абстрактную машину ^[1] , что манипулирует символы на полосу ленты в соответствии с таблицей правил. ^[2] Несмотря на простоту модели, для любого компьютерного алгоритма можно построить машину Тьюринга, способную моделировать логику этого алгоритма. ^[3]

Машина работает на бесконечной ^[4] ленте памяти, разделенной на дискретные «ячейки». ^[5] Машина помещает свою «голову» над ячейкой и «считывает» или «сканирует» ^[6] символ там. Затем, согласно символу и собственному текущему состоянию машины в «конечной таблице» ^[7] заданных пользователем инструкций, машина (i) записывает символ (например, цифру или букву из конечного алфавита) в ячейка (некоторые модели позволяют стирать символы или не писать), ^[8] затем (ii) либо перемещает ленту на одну ячейку влево или вправо (некоторые модели не допускают движения, некоторые модели перемещают головку), ^[9]затем (iii) (как определено наблюдаемым символом и собственным состоянием машины в таблице) либо переходит к следующей инструкции, либо останавливает вычисление. ^[10]

Машина Тьюринга была изобретена в 1936 году Алан Тьюринг , ^{[11] [12]} , который назвал его «а-машина» (автомат). ^[13] С помощью этой модели Тьюринг смог ответить на два вопроса отрицательно: (1) Существует ли машина, которая может определять, является ли любая произвольная машина на своей ленте «круговой» (например, зависает или не может продолжить свои вычисления? задача)? Точно так же (2) существует ли машина, которая может определить, печатает ли когда-либо произвольная машина на своей ленте заданный символ? ^{[14] [15]} Таким образом, предоставив математическое описание очень простого устройства, способного выполнять произвольные вычисления, он смог доказать свойства вычислений в целом - и, в частности, невычислимостьиз проблемы разрешения ( «решение проблемы»). ^[16]

Машины Тьюринга доказали существование фундаментальных ограничений мощности механических вычислений. ^[17] Хотя они могут выражать произвольные вычисления, их минималистский дизайн делает их непригодными для вычислений на практике: компьютеры реального мира основаны на различных конструкциях, которые, в отличие от машин Тьюринга, используют память с произвольным доступом .

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

Обзор [ править ]

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

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

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

Машина Тьюринга, способная моделировать любую другую машину Тьюринга, называется универсальной машиной Тьюринга (UTM или просто универсальной машиной). Более математически ориентированное определение с похожей «универсальной» природой было введено Алонзо Чёрчем , чьи работы по лямбда-исчислению переплелись с Тьюрингом в формальной теории вычислений, известной как тезис Чёрча – Тьюринга . В тезисе утверждается, что машины Тьюринга действительно улавливают неформальное понятие эффективных методов в логике и математике и дают точное определение алгоритма или «механической процедуры». Изучение их абстрактных свойствдает много идей в области информатики и теории сложности .

Физическое описание [ править ]

В своем эссе 1948 года «Интеллектуальные машины» Тьюринг писал, что его машина состоит из:

... неограниченный объем памяти, полученный в виде бесконечной ленты, размеченной квадратами, на каждом из которых может быть напечатан символ. В любой момент в автомате есть один символ; он называется отсканированным символом. Устройство может изменять отсканированный символ, и его поведение частично определяется этим символом, но символы на ленте в другом месте не влияют на поведение устройства. Однако ленту можно перемещать вперед и назад через машину, что является одной из элементарных операций машины. Следовательно, любой символ на ленте может иметь подачу. ^[18]

-  Тьюринг 1948, стр. 3 ^[19]

Описание [ править ]

Машина Тьюринга математически моделирует машину, которая механически работает с лентой. На этой ленте есть символы, которые машина может читать и записывать по одному с помощью ленточной головки. Работа полностью определяется конечным набором элементарных инструкций, таких как «в состоянии 42, если видимый символ равен 0, записать 1; если видимый символ равен 1, перейти в состояние 17; в состоянии 17, если видимый символ - 0, напишите 1 и перейдите в состояние 6; и т. д. В исходной статье (« О вычислимых числах в приложении к проблеме Entscheidungsproblem », см. также ссылки ниже ) Тьюринг представляет не механизм, а человека, которого он называет «компьютером», который рабски выполняет эти детерминированные механические правила. (или, как выразился Тьюринг, «бессистемно»).

Более точно, машина Тьюринга состоит из:

• Лента разделена на ячейки, один рядом с другим. Каждая ячейка содержит символ из некоторого конечного алфавита. Алфавит содержит специальный пустой символ (здесь записывается как «0») и один или несколько других символов. Предполагается, что лента может произвольно расширяться влево и вправо, так что машина Тьюринга всегда снабжается столько ленты, сколько ей нужно для ее вычислений. Предполагается, что ячейки, которые не были записаны ранее, заполнены пустым символом. В некоторых моделях лента имеет левый конец, отмеченный специальным символом; лента расширяется или неограниченно растягивается вправо.
• Головка , которая может читать и символы записи на ленте и переместить ленту влево и вправо один (и только один) клетки в то время. В некоторых моделях голова движется, а лента неподвижна.
• Государственный реестр , который хранит состояние машины Тьюринга, один из конечного числа. Среди них особое начальное состояние, с которым инициализируется регистр состояний. Эти состояния, как пишет Тьюринг, заменяют «состояние ума», в котором обычно находится человек, выполняющий вычисления.
• Конечная таблица ^[20] инструкции ^[21] , что, учитывая состояние (д _я ) машина в настоящее время , и символ (а _J ) он читает на ленте (символ в данный момент под головкой), сообщают машину к выполните следующие действия последовательно (для моделей с 5 кортежами):

1. Сотрите или напишите символ (заменив _j на _j1 ).
2. Переместите голову (что описывается d _k и может иметь значения: «L» для одного шага влево или «R» для одного шага вправо или «N» для пребывания на том же месте).
3. Примите то же или новое состояние, как предписано (перейдите в состояние q _i1 ).

В моделях с четырьмя кортежами стирание или запись символа (a _j1 ) и перемещение головы влево или вправо (d _k ) задаются как отдельные инструкции. Таблица указывает машине (ia) стереть или написать символ или (ib) переместить головку влево или вправо, а затем (ii) принять то же или новое состояние, как предписано, но не оба действия (ia) и (ib ) в той же инструкции. В некоторых моделях, если в таблице нет записи для текущей комбинации символа и состояния, автомат останавливается; другие модели требуют заполнения всех записей.

Каждая часть машины (то есть ее состояние, наборы символов и использованная лента в любой момент времени) и ее действия (такие как печать, стирание и движение ленты) конечны , дискретны и различимы ; это неограниченное количество ленты и времени выполнения, которые дают неограниченный объем дискового пространства .

Формальное определение [ править ]

Следуя Hopcroft & Ullman (1979 , стр. 148) , (однопленочная) машина Тьюринга может быть формально определена как кортеж из семи элементов, гдеОшибка harvtxt: цель отсутствует: CITEREFHopcroftUllman1979 ( справка ) ${\ Displaystyle M = \ langle Q, \ Gamma, b, \ Sigma, \ delta, q_ {0}, F \ rangle}$

• ${\ displaystyle Q}$- конечный непустой набор состояний ;
• ${\ displaystyle \ Gamma}$- конечный непустой набор символов ленточного алфавита ;
• ${\ displaystyle b \ in \ Gamma}$- пустой символ (единственный символ, который может встречаться на ленте бесконечно часто на любом этапе вычислений);
• ${\ Displaystyle \ Sigma \ substeq \ Gamma \ setminus \ {Ь \}}$- набор входных символов , то есть набор символов, разрешенных для появления в исходном содержимом ленты;
• ${\ displaystyle q_ {0} \ in Q}$- начальное состояние ;
• ${\ Displaystyle F \ substeq Q}$набор конечных состояний или принимающих состояний . Считается, что начальное содержимое ленты принято , если оно в конечном итоге остановится в состоянии от .${\ displaystyle M}$${\ displaystyle F}$
• ${\ displaystyle \ delta: (Q \ setminus F) \ times \ Gamma \ not \ to Q \ times \ Gamma \ times \ {L, R \}}$- частичная функция, называемая функцией перехода , где L - сдвиг влево, R - сдвиг вправо. Если не определено для текущего состояния и текущего символа ленты, машина останавливается; ^[22]${\ displaystyle \ delta}$

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

Относительно необычный вариант допускает «без сдвига», скажем, N в качестве третьего элемента набора направлений .${\ displaystyle \ {L, R \}}$

Кортеж из 7 занятых бобров с 3 состояниями выглядит так (подробнее об этом занятом бобре в примерах машины Тьюринга ):

• ${\ displaystyle Q = \ {{\ mbox {A}}, {\ mbox {B}}, {\ mbox {C}}, {\ mbox {HALT}} \}}$ (состояния);
• ${\ Displaystyle \ Gamma = \ {0,1 \}}$ (символы ленточного алфавита);
• ${\ displaystyle b = 0}$ (пустой символ);
• ${\ Displaystyle \ Sigma = \ {1 \}}$ (входные символы);
• ${\ displaystyle q_ {0} = {\ mbox {A}}}$ (начальное состояние);
• ${\displaystyle F=\{{\mbox{HALT}}\}}$ (конечные состояния);
• ${\displaystyle \delta =}$ см. таблицу состояний ниже (функция перехода).

Изначально все ячейки ленты отмечены значком .${\displaystyle 0}$

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

Дополнительные детали, необходимые для визуализации или реализации машин Тьюринга [ править ]

По словам ван Эмде Боаса (1990), стр. 6: «Теоретико-множественный объект [его формальное описание из семи кортежей, подобное приведенному выше] предоставляет лишь частичную информацию о том, как машина будет вести себя и как будут выглядеть ее вычисления».

Например,

• Потребуется множество решений о том, как на самом деле выглядят символы, и надежный способ чтения и записи символов на неопределенный срок.
• Операции сдвига влево и вправо могут сдвигать головку ленты поперек ленты, но при создании машины Тьюринга более практично вместо этого заставить ленту скользить вперед и назад под головкой.
• Лента может быть конечной и автоматически расширяться пробелами по мере необходимости (что наиболее близко к математическому определению), но чаще думают о ней как о бесконечно растягивающейся на одном или обоих концах и предварительно заполненной пробелами, кроме явно заданный конечный фрагмент, на котором находится головка ленты. (Это, конечно, нереализуемо на практике.) Ленту нельзя фиксировать по длине, поскольку это не соответствовало бы данному определению и серьезно ограничило бы диапазон вычислений, которые машина может выполнять, до вычислений линейно ограниченного автомата, если лента была пропорциональна входному размеру или конечному автомату, если она была строго фиксированной длины.

Альтернативные определения [ править ]

Определения в литературе иногда немного отличаются, чтобы сделать аргументы или доказательства проще или яснее, но это всегда делается таким образом, чтобы получившаяся машина имела ту же вычислительную мощность. Например, набор можно изменить с на , где N («Нет» или «Нет операции») позволит машине оставаться на той же ячейке ленты вместо перемещения влево или вправо. Это не увеличило бы вычислительную мощность машины.${\displaystyle \{L,R\}}$${\displaystyle \{L,R,N\}}$

Согласно соглашению Тьюринга / Дэвиса (Turing (1936) в The Undecidable , p. 126-127 and Davis (2000)), наиболее распространенное соглашение представляет каждую «инструкцию Тьюринга» в «таблице Тьюринга» одним из девяти 5-кортежей. стр.152):

(определение 1): (q _i , S _j , S _k / E / N, L / R / N, q _m )

( текущее состояние q _i , символ отсканирован S _j , символ печати S _k / стереть E / нет N , move_tape_one_square влево L / вправо R / нет N , новое состояние q _m )

Другие авторы (Мински (1967) стр. 119, Хопкрофт и Ульман (1979) стр. 158, Стоун (1972) стр. 9) принимают другое соглашение, с новым состоянием q _m, перечисленным сразу после отсканированного символа S _j :

(определение 2): (q _i , S _j , q _m , S _k / E / N, L / R / N)

( текущее состояние q _i , отсканированный символ S _j , новое состояние q _m , символ печати S _k / стереть E / нет N , move_tape_one_square влево L / вправо R / нет N )

В оставшейся части этой статьи будет использоваться «определение 1» (соглашение Тьюринга / Дэвиса).

В следующей таблице исходная модель Тьюринга допускала только первые три строки, которые он назвал N1, N2, N3 (см. Тьюринг в книге «Неразрешимость» , стр. 126). Он разрешил стирание «отсканированного квадрата», назвав 0-й символ S ₀ = «стереть» или «пустой» и т. Д. Однако он не разрешил непечать, поэтому каждая строка команд включает «символ печати S _k. "или" стереть "(см. сноску 12 в Post (1947), The Undecidable , p. 300). Это аббревиатуры Тьюринга ( The Undecidable , p. 119). Вслед за оригинальной статьей Тьюринга в 1936–1937 годах, модели машин допускали все девять возможных типов кортежей из пяти:

Любая таблица Тьюринга (список инструкций) может быть построена из приведенных выше девяти кортежей. По техническим причинам обычно можно обойтись без трех непечатаемых инструкций или «N» (4, 5, 6). Примеры см. В примерах машины Тьюринга .

Реже встречаются 4-кортежи: они представляют собой дальнейшую атомизацию инструкций Тьюринга (см. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); также см. больше на машине Пост-Тьюринга .

"Состояние" [ править ]

Слово «состояние», используемое в контексте машин Тьюринга, может быть источником путаницы, поскольку оно может означать две вещи. Большинство комментаторов после Тьюринга использовали «состояние» для обозначения имени / обозначения текущей инструкции, которая должна быть выполнена, то есть содержимого регистра состояний. Но Тьюринг (1936) провел четкое различие между записью того, что он назвал «m-конфигурацией» машины, и «состоянием прогресса» машины (или человека) посредством вычислений - текущим состоянием всей системы. То, что Тьюринг назвал «формулой состояния», включает в себя как текущую инструкцию, так и все символы на ленте:

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

-  The Undecidable , pp. 139–140, курсив мой.

Ранее в своей статье Тьюринг пошел еще дальше: он приводит пример, в котором он поместил символ текущей «m-конфигурации» - метку инструкции - под отсканированным квадратом вместе со всеми символами на ленте ( The Undecidable , p. 121); он называет это « полной конфигурацией » ( «Неразрешимое» , стр. 118). Чтобы напечатать «полную конфигурацию» в одной строке, он помещает метку состояния / m-конфигурацию слева от отсканированного символа.

Вариант этого можно увидеть у Клини (1952), где Клини показывает, как записать число Гёделя «ситуации» машины: он помещает символ «m-конфигурации» q ₄ над отсканированным квадратом примерно в центре 6 не -завершите квадраты на ленте (см. фигуру ленты Тьюринга в этой статье) и поместите ее справа от сканируемого квадрата. Но Клини называет само q ₄ «машинным состоянием» (Клини, стр. 374-375). Хопкрофт и Уллман называют эту композицию «мгновенным описанием» и следуют соглашению Тьюринга о размещении «текущего состояния» (метка инструкции, m-конфигурация) слева от отсканированного символа (стр. 149).

Пример: общее состояние 3-значного 2-значного занятого бобра после 3 «ходов» (взято из примера «бег» на рисунке ниже):

1 А 1

Это означает: после трех ходов ленты имеет ... 000110000 ... на него, голова сканирование самого правая 1 и состояние . Пробелы (в данном случае представленные «0») могут быть частью общего состояния, как показано здесь: B 01; лента имеет единственную 1 на ней, но головка сканирует 0 ( «пустой») на его левой и состояние B .

«Состояние» в контексте машин Тьюринга следует пояснить относительно того, что описывается: ( i ) текущая инструкция, или ( ii ) список символов на ленте вместе с текущей инструкцией, или ( iii ) список символы на ленте вместе с текущей инструкцией, помещенной слева от отсканированного символа или справа от отсканированного символа.

Биограф Тьюринга Эндрю Ходжес (1983: 107) отметил и обсудил эту путаницу.

Диаграммы "состояний" машины Тьюринга [ править ]

Справа: приведенная выше таблица в виде диаграммы «перехода между состояниями».

Обычно большие столы лучше оставлять как столы (Бут, стр. 74). Их легче моделировать на компьютере в табличной форме (Бут, стр. 74). Однако некоторые концепции - например, машины с состояниями «перезагрузки» и машины с повторяющимися шаблонами (см. Hill and Peterson, стр. 244ff) - легче увидеть, если рассматривать их как чертеж.

Читатель должен решить, представляет ли рисунок улучшение таблицы в конкретном контексте. См. Конечный автомат для получения дополнительной информации.

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

Диаграмма «Ход вычислений» показывает прогресс «состояния» (инструкции) активного бобра с тремя состояниями в ходе вычислений от начала до конца. Справа находится «полная конфигурация» Тьюринга («ситуация» Клини, «мгновенное описание» Хопкрофта – Ульмана) на каждом этапе. Если бы машину нужно было остановить и очистить, чтобы очистить как «регистр состояний», так и всю ленту, эти «конфигурации» можно было бы использовать для повторного запуска вычислений в любом месте их выполнения (см. Turing (1936) The Undecidable , pp. 139–1). 140).

Модели, эквивалентные модели машины Тьюринга [ править ]

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

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

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

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

Доступные только для чтения машины Тьюринга с правым движением эквивалентны DFA (а также NFA путем преобразования с использованием алгоритма преобразования NDFA в DFA ).

Для практических и дидактических целей эквивалентная регистровая машина может использоваться как обычный язык программирования ассемблера .

Интересен вопрос, является ли вычислительная модель, представленная конкретными языками программирования, эквивалентом Тьюринга. Хотя вычисления на реальном компьютере основаны на конечных состояниях и, следовательно, не способны моделировать машину Тьюринга, сами языки программирования не обязательно имеют это ограничение. Kirner et al., 2009 показали, что среди языков программирования общего назначения некоторые являются полными по Тьюрингу, а другие - нет. Например, ANSI C не является эквивалентом по Тьюрингу, поскольку все экземпляры ANSI C (возможны различные экземпляры, поскольку стандарт намеренно оставляет определенное поведение неопределенным по причинам устаревшего характера) подразумевает память с конечным пространством. Это связано с тем, что размер ссылочных типов данных памяти, называемых указателями, доступен внутри языка. Однако другие языки программирования, такие как Паскаль , не имеют этой функции, что позволяет им быть в принципе полными по Тьюрингу. В принципе, это просто завершение по Тьюрингу, поскольку при выделении памяти на языке программирования допускается сбой, что означает, что язык программирования может быть завершенным по Тьюрингу при игнорировании неудачных выделений памяти, но скомпилированные программы, выполняемые на реальном компьютере, не могут.

Выбор c-машин, oracle o-машин [ править ]

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

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

-  Неразрешимое , с. 118

Тьюринг (1936) не делает дальнейших подробностей, за исключением сноски, в которой он описывает, как использовать a-машину, чтобы «найти все доказуемые формулы исчисления [Гильберта]», а не использовать машину выбора. Он «предполагает [s], что выбор всегда находится между двумя вариантами 0 и 1. Каждое доказательство будет определяться последовательностью вариантов i ₁ , i ₂ , ..., i _n (i ₁ = 0 или 1, i ₂ = 0 или 1, ..., i _n = 0 или 1), следовательно, число 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... + i _nполностью определяет доказательство. Автомат последовательно выполняет доказательство 1, доказательство 2, доказательство 3, ... »(Сноска ‡, Неразрешимое , стр. 138)

Это действительно метод, с помощью которого можно использовать детерминированную (т. Е. А-) машину Тьюринга для имитации действия недетерминированной машины Тьюринга ; Тьюринг решил этот вопрос в сноске и, похоже, исключил его из дальнейшего рассмотрения.

Оракул машина или о-машин Тьюринг а-машина , которая приостанавливает свои вычисления в состоянии « о » , а, чтобы завершить свои расчеты, он «ждет решений» из «оракула» -an неопределенных лиц « , кроме говоря , что не может быть машиной »(Turing (1939), The Undecidable , p. 166–168).

Универсальные машины Тьюринга [ править ]

Как писал Тьюринг в «Неразрешаемом» , стр. 128 (курсив добавлен):

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

Это открытие сейчас считается само собой разумеющимся, но в то время (1936 г.) оно считалось поразительным. Модель вычислений, которую Тьюринг назвал своей «универсальной машиной» - для краткости « U », - рассматривается некоторыми (см. Davis (2000)) как фундаментальный теоретический прорыв, который привел к появлению концепции компьютера с хранимой программой .

Статья Тьюринга ... содержит, по сути, изобретение современного компьютера и некоторых сопровождающих его методов программирования.

-  Минский (1967), с. 104

С точки зрения вычислительной сложности многоленточная универсальная машина Тьюринга должна быть медленнее только на логарифмический коэффициент по сравнению с машинами, которые она моделирует. Этот результат был получен в 1966 году FC Hennie и RE Stearns . (Арора, Барак, 2009, теорема 1.9)

Наименьшая возможная универсальная машина Тьюринга имеет 2 состояния и 3 символа, машина Тьюринга с 2 состояниями и 3 символами Вольфрама . Доказательство универсальности стоило 25000 долларов.

Сравнение с реальными машинами [ править ]

Часто говорят ^{[ кем? ],} что машины Тьюринга, в отличие от более простых автоматов, столь же мощны, как и настоящие машины, и способны выполнять любую операцию, которую может выполнять настоящая программа. В этом утверждении пренебрегают тем, что, поскольку реальная машина может иметь только конечное число конфигураций , эта «настоящая машина» на самом деле не что иное, как конечный автомат . С другой стороны, машины Тьюринга эквивалентны машинам, у которых есть неограниченный объем памяти для своих вычислений.

Есть несколько способов объяснить, почему машины Тьюринга являются полезными моделями реальных компьютеров:

1. Все, что может вычислить настоящий компьютер, может вычислить и машина Тьюринга. Например: «Машина Тьюринга может моделировать подпрограммы любого типа, имеющиеся в языках программирования, включая рекурсивные процедуры и любой из известных механизмов передачи параметров» (Хопкрофт и Ульман, стр. 157). Достаточно большой FSA может также смоделировать любой реальный компьютер, не обращая внимания на ввод-вывод. Таким образом, утверждение об ограничениях машин Тьюринга применимо и к реальным компьютерам.
2. Разница заключается только в способности машины Тьюринга манипулировать неограниченным объемом данных. Однако, учитывая конечное количество времени, машина Тьюринга (как и настоящая машина) может манипулировать только конечным объемом данных.
3. Как и в случае с машиной Тьюринга, на реальной машине можно по мере необходимости увеличивать объем памяти, приобретая больше дисков или других носителей.
4. Описание реальных машинных программ с использованием более простых абстрактных моделей часто намного сложнее, чем описания с использованием машин Тьюринга. Например, машина Тьюринга, описывающая алгоритм, может иметь несколько сотен состояний, в то время как эквивалентный детерминированный конечный автомат (DFA) на данной реальной машине имеет квадриллионы. Это делает невозможным анализ представления DFA.
5. Машины Тьюринга описывают алгоритмы независимо от того, сколько памяти они используют. Существует предел памяти, которой обладает любая текущая машина, но этот предел может произвольно увеличиваться со временем. Машины Тьюринга позволяют нам делать утверждения об алгоритмах, которые (теоретически) сохранятся вечно, независимо от достижений в архитектуре обычных вычислительных машин.
6. Машины Тьюринга упрощают формулировку алгоритмов. Алгоритмы, работающие на абстрактных машинах, эквивалентных Тьюрингу, обычно более общие, чем их аналоги, работающие на реальных машинах, потому что они имеют доступные типы данных произвольной точности и никогда не должны иметь дело с неожиданными условиями (включая, помимо прочего, нехватку памяти ) .

Ограничения машин Тьюринга [ править ]

Теория вычислительной сложности [ править ]

Ограничение машин Тьюринга заключается в том, что они плохо моделируют сильные стороны конкретной системы. Например, современные компьютеры с хранимой программой на самом деле являются экземплярами более конкретной формы абстрактной машины, известной как машина с хранимой программой с произвольным доступом или модель машины RASP. Подобно универсальной машине Тьюринга , RASP хранит свою «программу» в «памяти», внешней по отношению к «инструкциям» своего конечного автомата. В отличие от универсальной машины Тьюринга, RASP имеет бесконечное количество различимых, пронумерованных, но неограниченных «регистров» - «ячеек» памяти, которые могут содержать любое целое число (см. Элгот и Робинсон (1964), Хартманис (1971) и, в частности, Кука). -Rechow (1973); ссылки на машину с произвольным доступом). Конечный автомат RASP снабжен возможностью косвенной адресации (например, содержимое одного регистра может использоваться как адрес для указания другого регистра); таким образом, «программа» RASP может обращаться к любому регистру в последовательности регистров. Результатом этого различия является то, что существуют вычислительные оптимизации, которые могут быть выполнены на основе индексов памяти, что невозможно в обычной машине Тьюринга; таким образом, когда машины Тьюринга используются в качестве основы для ограничения времени работы, «ложная нижняя граница» может быть доказана на временах работы определенных алгоритмов (из-за ложного упрощающего предположения машины Тьюринга). Примером этого является бинарный поиск, алгоритм, который может работать быстрее при использовании модели вычислений RASP, а не модели машины Тьюринга.

Параллелизм [ править ]

Еще одно ограничение машин Тьюринга состоит в том, что они плохо моделируют параллелизм. Например, существует ограничение на размер целого числа, которое может быть вычислено постоянно останавливающейся недетерминированной машиной Тьюринга, запускающейся с пустой ленты. (См. Статью о неограниченном недетерминизме .) Напротив, существуют постоянно останавливающиеся параллельные системы без входных данных, которые могут вычислять целое число неограниченного размера. (Процесс может быть создан с локальным хранилищем, которое инициализируется счетчиком 0, который одновременно отправляет себе как сообщение остановки, так и сообщение перехода. Когда он получает сообщение перехода, он увеличивает его счетчик на 1 и отправляет себе сообщение перехода. он получает сообщение об остановке, он останавливается с неограниченным числом в своем локальном хранилище.)

Взаимодействие [ править ]

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

С 1970-х годов интерактивное использование компьютеров стало гораздо более распространенным. В принципе, это можно смоделировать, если внешний агент будет читать с ленты и записывать на нее одновременно с машиной Тьюринга, но это редко соответствует тому, как на самом деле происходит взаимодействие; поэтому при описании интерактивности обычно предпочтительны такие альтернативы, как автоматы ввода-вывода .

История [ править ]

Они были описаны в 1936 году Аланом Тьюрингом .

Историческая справка: вычислительная техника [ править ]

Робин Ганди (1919–1995) - ученик Алана Тьюринга (1912–1954) и его давний друг - прослеживает происхождение понятия «вычислительная машина» от Чарльза Бэббиджа (около 1834 г.) и фактически предлагает «Тезис Бэббиджа» :

Что все процессы разработки и анализа теперь могут выполняться машинами .

-  (курсив Бэббиджа, цит. По Ганди, стр. 54)

Анализ Gandy по Бэббиджу аналитической машины описывается следующие пять операций (ср р 52-53.):

1. Арифметические функции +, -, ×, где - указывает на «правильное» вычитание x - y = 0, если y ≥ x .
2. Любая последовательность операций - это операция.
3. Итерация операции (повторение операции P n раз).
4. Условная итерация (повторение n раз операции P при условии «успеха» теста T).
5. Условный перевод (т. Е. Условный переход ).

Ганди утверждает, что «функции, которые могут быть вычислены с помощью (1), (2) и (4), являются в точности теми, которые вычислимы по Тьюрингу ». (стр.53). Он цитирует другие предложения относительно «универсальных вычислительных машин», в том числе предложения Перси Ладгейта (1909), Леонардо Торреса и Кеведо (1914), Мориса д'Окань (1922), Луи Куффиньяла (1933), Ванневара Буша (1936), Говарда Эйкена ( 1937 г.). Тем не мение:

… Упор делается на программирование фиксированной повторяющейся последовательности арифметических операций. Фундаментальная важность условной итерации и условного переноса для общей теории вычислительных машин не признается ...

-  Ганди П. 55

Entscheidungsproblem («проблема решения»): десятый вопрос Гильберта 1900 г. [ править ]

Что касается проблем Гильберта, поставленных известным математиком Дэвидом Гильбертом в 1900 году, один из аспектов проблемы № 10 витал в воздухе почти 30 лет, прежде чем он был точно сформулирован. Исходное выражение Гильберта для № 10 выглядит следующим образом:

10. Определение разрешимости диофантова уравнения . Дано диофантово уравнение с любым количеством неизвестных величин и с рациональными интегральными коэффициентами: разработать процесс, согласно которому с помощью конечного числа операций можно определить, разрешимо ли уравнение в целых рациональных числах. Entscheidungsproblem [проблема решения для логики первого порядка ] решается, когда мы знаем процедуру, которая позволяет любому заданному логическому выражению определять с помощью конечного числа операций его достоверность или выполнимость ... Entscheidungsproblem следует рассматривать как главную проблему математической логики.

-  цитируется с этим переводом и оригиналом на немецком языке в Dershowitz and Gurevich, 2008 г.

К 1922 г. это понятие « Entscheidungsproblem » немного развилось, и Х. Беманн заявил, что

... наиболее общая форма Entscheidungsproblem [выглядит] следующим образом:

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

-  Ганди П. 57, цитируя Бемана

Беманн отмечает, что ... общая проблема эквивалентна проблеме определения истинности математических утверждений.

-  там же.

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

-  там же. , п. 92

К Международному конгрессу математиков 1928 года Гильберт «сделал свои вопросы достаточно точными. Во-первых, была ли математика завершена ... Во-вторых, была ли математика последовательной ... И в-третьих, была ли математика разрешимой ?» (Ходжес, стр. 91, Хокинг, стр. 1121). На первые два вопроса в 1930 году ответил Курт Гёдель на том же собрании, где Гильберт произнес свою пенсионную речь (к большому огорчению Гильберта); третью - проблему Entscheidungspro - пришлось отложить до середины 1930-х годов.

Проблема заключалась в том, что для ответа сначала требовалось точное определение « определенного общего применимого предписания », которое принстонский профессор Алонзо Черч назвал « эффективной вычислимостью », а в 1928 году такого определения не существовало. Но в течение следующих 6-7 лет Эмиль Пост разработал свое определение рабочего, перемещающегося из комнаты в комнату, пишущего и стирая отметки в соответствии со списком инструкций (Post 1936), как и Черч и два его ученика Стивен Клини и Дж. Б. Россер , используя Лямбда-исчисление Черча и теория рекурсии Гёделя(1934). Статья Черча (опубликованная 15 апреля 1936 г.) показала, что проблема Entscheidungsprost действительно «неразрешима» и опередила Тьюринга почти на год (статья Тьюринга, представленная 28 мая 1936 г., опубликована в январе 1937 г.). Тем временем Эмиль Пост осенью 1936 года представил краткую статью, так что Тьюринг имел по крайней мере приоритет перед Постом. Пока Черч ссылался на статью Тьюринга, Тьюринг успел изучить статью и добавить приложение, в котором он набросал доказательство того, что лямбда-исчисление Черча и его машины будут вычислять одни и те же функции.

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

-  Ходжес стр. 112

Пост только предложил определение исчисляемости и критиковал «определение» Черча, но ничего не доказал.

А-машина Алана Тьюринга [ править ]

Весной 1935 года Тьюринг, будучи молодым магистрантом Королевского колледжа Кембриджа , Великобритания , принял вызов; он был вдохновлен лекциями логика М.А. Ньюмана «и узнал от них о работе Гёделя и Entscheidungsproblem ... Ньюман использовал слово« механический »... В своем некрологе к Тьюрингу 1955 года Ньюман пишет:

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

-  Ганди, с. 74

Ганди заявляет, что:

Я полагаю, но не знаю, что Тьюринг с самого начала своей работы ставил своей целью доказательство неразрешимости Entscheidungsproblem. Он сказал мне, что «основная идея» статьи пришла к нему, когда он лежал на лугах Грантчестера летом 1935 года. «Основная идея» могла заключаться либо в его анализе вычислений, либо в его понимании того, что существует универсальная машина. , и, следовательно, диагональный аргумент для доказательства неразрешимости.

-  там же. , п. 76

Хотя Ганди считал, что приведенное выше заявление Ньюмана «вводит в заблуждение», это мнение разделяют не все. Тьюринг всю жизнь интересовался машинами: «Алан мечтал изобрести пишущие машинки в детстве; у [его матери] миссис Тьюринг была пишущая машинка; и он вполне мог начать с того, что спросил себя, что означает называть пишущую машинку« механической »». (Ходжес стр.96). Работая над докторской степенью в Принстоне, Тьюринг построил логический множитель (см. Ниже). Его кандидатская диссертация, озаглавленная « Системы логики на основе порядковых чисел », содержит следующее определение «вычислимой функции»:

Выше было сказано, что «функция эффективно вычислима, если ее значения могут быть найдены с помощью некоторого чисто механического процесса». Мы можем понимать это утверждение буквально, понимая чисто механический процесс, который может быть осуществлен машиной. Можно дать математическое описание в определенной нормальной форме структур этих машин. Развитие этих идей приводит к определению автором вычислимой функции и отождествлению вычислимости с эффективной вычислимостью. Нетрудно, хотя и несколько утомительно, доказать, что эти три определения [3-е - λ-исчисление] эквивалентны.

-  Тьюринг (1939) в The Undecidable , p. 160

Когда Тьюринг вернулся в Великобританию, он в конечном итоге стал совместно ответственным за взлом немецких секретных кодов, созданных шифровальными машинами под названием «Загадка»; он также стал участвовать в разработке ACE ( Automatic Computing Engine ), «предложение ACE [Тьюринга] было фактически самодостаточным, и его корни лежали не в EDVAC [инициативе США], а в его собственной универсальной машине» ( Ходжес стр. 318). Споры о происхождении и природе того, что было названо Тезисом Тьюринга Клини (1952), все еще продолжаются . Но то, что Тьюринг доказал с помощью своей модели вычислительной машины, появляется в его статье « О вычислимых числах в приложении к проблеме Entscheidungsproblem » (1937 г.):

[что] проблема Hilbert Entscheidungs ​​не может иметь решения ... Поэтому я предлагаю показать, что не может быть общего процесса для определения того, является ли данная формула U функционального исчисления K доказуемой, то есть что не может быть машины, которая, снабженный любой из этих формул U, в конечном итоге скажет, доказуемо ли U.

-  из статьи Тьюринга, перепечатанной в The Undecidable , p. 145

Пример Тьюринга (его второе доказательство): если кто-то попросит общую процедуру, чтобы сказать нам: «Эта машина когда-либо печатает 0», вопрос будет «неразрешимым».

1937–1970: «цифровой компьютер», рождение «информатики» [ править ]

В 1937 году, когда в Принстоне работал над своей докторской диссертацией, Тьюринг с нуля построил цифровой (логический) умножитель, сделав свои собственные электромеханические реле (Ходжес, стр. 138). «Задачей Алана было воплотить логический замысел машины Тьюринга в сети переключателей с релейным управлением ...» (Ходжес, стр. 138). Хотя Тьюринг, возможно, изначально был просто любопытным и экспериментировал, довольно серьезная работа в том же направлении велась в Германии ( Конрад Цузе (1938)), а также в Соединенных Штатах ( Говард Эйкен ) и Джордж Стибиц (1937); плоды их труда использовались вооруженными силами как Оси, так и союзников во Второй мировой войне (см. Ходжес, стр. 298–299). В начале и середине 1950-х годов Хао Ван иМарвин Мински уменьшили машину Тьюринга к более простой форме (предшественник к машине после Тьюринга от Martin Davis ); Одновременно европейские исследователи сводили новомодный электронный компьютер к теоретическому объекту, подобному компьютеру, эквивалентному тому, что теперь называли «машиной Тьюринга». В конце 1950-х - начале 1960-х годов совпадающие параллельные разработки Мелзака и Ламбека (1961), Мински (1961) и Шепердсона и Стерджиса (1961) продвинули европейские исследования дальше и свели машину Тьюринга к более дружественной, компьютерной. абстрактная модель, называемая счетной машиной ; Элгот и Робинсон (1964), Хартманис (1971), Кук и Рекхоу (1973) продвинули эту работу еще дальше смодели регистровой машины и машины с произвольным доступом - но в основном все это просто многоленточные машины Тьюринга с набором инструкций, подобным арифметике.

1970 – настоящее время: машина Тьюринга как модель вычислений [ править ]

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

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

автономная многоленточная машина Тьюринга ..., которая представляет собой стандартную модель для строково-ориентированных вычислений, и машину с произвольным доступом (RAM), представленную Куком и Рекком ..., которая моделирует идеализированный компьютер в стиле фон Неймана.

-  ван Эмде Боас 1990: 4

Только в смежной области анализа алгоритмов эту роль берет на себя модель RAM.

-  ван Эмде Боас 1990: 16

См. Также [ править ]

Примечания [ править ]

1. ^ Minsky 1967: 107 "В своей статье 1936 года AM Тьюринг определил класс абстрактных машин, которые теперь носят его имя. Машина Тьюринга - это машина с конечным числом состояний, связанная с особым видом среды - ее лентой, - в которой она может сохранять (а позже восстанавливать) последовательности символов », также Stone 1972: 8, где слово« машина »заключено в кавычки.
2. ^ Stone 1972: 8 утверждает: «Эта« машина »является абстрактной математической моделью», также ср. Sipser 2006: 137ff, описывающий «модель машины Тьюринга». Rogers 1987 (1967): 13 относится к «характеристике Тьюринга», Boolos Burgess и Jeffrey 2002: 25 относится к «особому виду идеализированной машины».
3. ^ Sipser 2006: 137 «Машина Тьюринга может делать все, что может делать настоящий компьютер».
4. ^ Ср. Сипсер 2002: 137. Кроме того, Rogers 1987 (1967): 13 описывает «бумажную ленту бесконечной длины в обоих направлениях». Минский 1967: 118 утверждает: «Лента считается бесконечной в обоих направлениях». Boolos Burgess и Jeffrey 2002: 25 включают возможность, что «на каждом конце стоит кто-нибудь, чтобы добавить дополнительные пустые квадраты по мере необходимости».
5. ^ Ср. Роджерс 1987 (1967): 13. Другие авторы используют слово «квадрат», например, Boolos Burgess Jeffrey 2002: 35, Minsky 1967: 117, Penrose 1989: 37.
6. ^ Это слово используется, например, Davis 2000: 151
7. ^ Эта таблица представляет алгоритм или «эффективную вычислительную процедуру», которая обязательно конечна; см. Penrose 1989: 30ff, Stone 1972: 3ff.
8. ^ Boolos Burgess и Джеффри 2002: 25
9. ^ Boolos Burgess Jeffry 2002: 25 иллюстрируют машинукак движется вдоль ленты. Пенроуз 1989: 36-37 описывает себя как «неудобно» с бесконечной лентой, замечающей, что «может быть трудно переключить!»; он «предпочитает [s] думать о ленте как о представлении некоторой внешней среды, через которую наше конечное устройство может перемещаться» и после наблюдения, что «« движение »является удобным способом изображения вещей», а затем предполагает, что «устройство получает все его вход из этой среды.
10. ^ «Также по соглашению одно из состояний выделяется как состояние остановки и получает название HALT» (Stone 1972: 9). Первоначальное описание Тьюринга не включало команду HALT, но он допускал «круговое» условие, «конфигурацию, из которой невозможно движение» (см. Turing 1936 в The Undecidable 1967: 119); это понятие было добавлено в 1950-е годы; подробнее см. в разделе Проблема с остановкой .
11. ^ Ходжес, Эндрю (2012). Алан Тьюринг: Загадка (Столетие изд.). Издательство Принстонского университета . ISBN 978-0-691-15564-7.
12. ↑ Идея пришла к нему в середине 1935 года (возможно, см. Больше в разделе «История») после вопроса, заданного М.Х.А. Ньюманом в его лекциях: «Существовал ли определенный метод, или, как выразился Ньюман,« механический процесс », который может быть применено к математическому утверждению и даст ответ на вопрос, доказуемо ли оно »(Hodges 1983: 93). Тьюринг представил свою статью 31 мая 1936 г. в Лондонское математическое общество для ознакомления с ней (см. Hodges 1983: 112), но она была опубликована в начале 1937 г., а оттиски были доступны в феврале 1937 г. (см. Hodges 1983: 129).
13. ↑ См. Сноску в Davis 2000: 151.
14. ^ Тьюринг 1936 в The Undecidable 1965: 132-134; Определение «кругового», данное Тьюрингом, можно найти на странице 119.
15. ^ Тьюринг, Алан Матисон (1937). «О вычислимых числах в приложении к Entscheidungsproblem» . Труды Лондонского математического общества, серия 2 . 42 (1): 230–265. DOI : 10.1112 / plms / s2-42.1.230 .- Перепечатка: Тьюринг, Алан. «О вычислимых числах с приложением к Entscheidungsproblem» . Цифровой архив Тьюринга . Дата обращения 9 июля 2020 .
16. ^ Тьюринг 1936 в The Undecidable 1965: 145
17. ^ Sipser 2006: 137 отмечает, что «машина Тьюринга может делать все, что может делать настоящий компьютер. Тем не менее, даже машина Тьюринга не может решить определенные проблемы. В самом реальном смысле эти проблемы выходят за теоретические пределы вычислений».
18. ^ См. Определение " подач " в Викисловаре.
19. ↑ AM Turing (июль 1948 г.). Интеллектуальные машины (Отчет). Национальная физическая лаборатория. Здесь: стр.3-4
20. ^ Иногда вызывается таблицей действий или функцией перехода .
21. ^ Обычно пятерки [5-кортежи]: q _i a _j → q _i1 a _j1 d _k , но иногда четверки [4-кортежи].
22. ^ с.149; в частности, Хопкрофт и Ульман предполагают, чтоон не определен на всех состояниях из${\displaystyle \delta }$${\displaystyle F}$

Ссылки [ править ]

Эта статья имеет нечеткий стиль цитирования . Используемые ссылки можно сделать более ясными с помощью другого или последовательного стиля цитирования и сносок . ( Ноябрь 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Первичная литература, оттиски и сборники [ править ]

• Б. Джек Коупленд изд. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7 . Содержит документы Тьюринга, а также черновик письма Эмилю Посту по поводу его критики "соглашения Тьюринга" и поправки Дональда У. Дэвиса к универсальной вычислительной машине Тьюринга. 
• Мартин Дэвис (редактор) (1965), Неразрешимый , Raven Press, Hewlett, NY.
• Эмиль Пост (1936), «Конечные комбинаторные процессы - формулировка 1», Journal of Symbolic Logic , 1, 103–105, 1936. Перепечатано в The Undecidable , pp. 289ff.
• Эмиль Пост (1947), «Рекурсивная неразрешимость проблемы Туэ», Журнал символической логики , т. 12. С. 1–11. Перепечатано в The Undecidable , pp. 293ff. В Приложении к этой статье Выложите комментарии и исправьте статью Тьюринга 1936–1937 годов. В частности, см. Сноски 11 с поправками к кодированию универсальной вычислительной машины и сноску 14 с комментариями к первому и второму доказательствам Тьюринга .
• Тьюринг, AM (1936). «О вычислимых числах в приложении к Entscheidungsproblem». Труды Лондонского математического общества . 2 (опубликовано в 1937 г.). 42 : 230–265. DOI : 10.1112 / plms / s2-42.1.230 .(и Тьюринг, AM (1938). «О вычислимых числах, с приложением к Entscheidungsproblem: исправление». Труды Лондонского математического общества . 2 (опубликовано в 1937 г.). 43 (6): 544–6. doi : 10.1112) /plms/s2-43.6.544 .). Перепечатано во многих сборниках, например, в The Undecidable , pp. 115–154; доступны в Интернете во многих местах.
• Алан Тьюринг, 1948, «Интеллектуальные машины». Перепечатано в «Кибернетике: ключевые статьи». Эд. CR Evans и ADJ Robertson. Балтимор: University Park Press, 1968. стр. 31. Перепечатано в Turing, AM (1996). «Интеллектуальные машины, еретическая теория». Philosophia Mathematica . 4 (3): 256–260. DOI : 10.1093 / philmat / 4.3.256 .
• ФК Хенни и Р. Э. Стернс . Двухленточное моделирование многоленточных машин Тьюринга . JACM , 13 (4): 533–546, 1966.

Теория вычислимости [ править ]

• Булос, Джордж; Ричард Джеффри (1999) [1989]. Вычислимость и логика (3-е изд.). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-20402-X.
• Булос, Джордж; Джон Берджесс; Ричард Джеффри (2002). Вычислимость и логика (4-е изд.). Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-00758-5.Некоторые части были существенно переписаны Бёрджессом. Представление машин Тьюринга в контексте «машин счётов» Ламбека (ср. Регистровая машина ) и рекурсивных функций , показывающая их эквивалентность.
• Тейлор Л. Бут (1967), Теория последовательных машин и автоматов , John Wiley and Sons, Inc., Нью-Йорк. Технический текст для выпускников; охватывает широкий круг вопросов, глава IX « Машины Тьюринга» включает некоторые теории рекурсии.
• Мартин Дэвис (1958). Вычислимость и неразрешимость . McGraw-Hill Book Company, Inc., Нью-Йорк.. На страницах 12–20 он приводит примеры таблиц из 5 кортежей для сложения, функции-преемника, вычитания (x ≥ y), правильного вычитания (0, если x <y), функции идентичности и различных функций идентичности и умножения.
• Дэвис, Мартин; Рон Сигал; Элейн Дж. Вейкер (1994). Вычислимость, сложность, языки и логика: основы теоретической информатики (2-е изд.). Сан-Диего: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.
• Хенни, Фредрик (1977). Введение в вычислимость . Аддисон-Уэсли, Рединг, Массачусетс, QA248.5H4 1977.. На страницах 90–103 Хенни обсуждает UTM с примерами и блок-схемами, но без реального «кода».
• Джон Хопкрофт и Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли, штат Массачусетс, Массачусетс, ISBN 0-201-02988-X. В центре внимания проблемы машинной интерпретации «языков», NP-полноты и т. Д.
• Хопкрофт, Джон Э .; Раджив Мотвани; Джеффри Д. Ульман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Месса для чтения: Аддисон – Уэсли. ISBN 0-201-44124-1. Совершенно иной и менее устрашающий, чем первое издание.
• Стивен Клини (1952), Введение в метаматематику , издательство North-Holland Publishing Company, Амстердам, Нидерланды, 10-е впечатление (с исправлениями из 6-го переиздания 1971 г.). Текст уровня выпускника; Большая часть главы XIII « Вычислимые функции» посвящена доказательствам вычислимости рекурсивных функций на машине Тьюринга и т. д.
• Кнут, Дональд Э. (1973). Том 1 / Фундаментальные алгоритмы: Искусство программирования (2-е изд.). Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company.. Относительно роли машин Тьюринга в развитии вычислений (как аппаратных, так и программных) см. 1.4.5 История и библиография, стр. 225ff и 2.6 История и библиография, стр. 456ff.
• Зохар Манна , 1974, Математическая теория вычислений . Перепечатано, Дувр, 2003. ISBN 978-0-486-43238-0 
• Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967. См. Главу 8, раздел 8.2 «Неразрешимость проблемы остановки». Отлично, т.е. относительно читабельно, иногда забавно.
• Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1. Глава 2: Машины Тьюринга, стр. 19–56.
• Хартли Роджерс младший , Теория рекурсивных функций и эффективной вычислимости , MIT Press, Кембридж, Массачусетс, издание в мягкой обложке, 1987 г., оригинальное издание Макгроу-Хилла, 1967 г., ISBN 0-262-68052-1 (pbk.) 
• Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X. Глава 3: Тезис Черча – Тьюринга, стр. 125–149.
• Стоун, Гарольд С. (1972). Введение в компьютерную организацию и структуры данных (1-е изд.). Нью-Йорк: Книжная компания Макгроу-Хилл. ISBN 0-07-061726-0.
• Питер ван Эмде Боас 1990, Модели машин и моделирование , стр. 3–66, в издании Яна ван Леувена , Справочник по теоретической информатике, том A: Алгоритмы и сложность , MIT Press / Elsevier, [место?], ISBN 0-444-88071-2 (Том А). QA76.H279 1990. Ценный обзор, содержащий 141 ссылку. 

Тезис Черча [ править ]

• Нахум Дершовиц; Юрий Гуревич (сентябрь 2008 г.). «Естественная аксиоматизация вычислимости и доказательство тезиса Черча» (PDF) . Вестник символической логики . 14 (3) . Проверено 15 октября 2008 .
• Роджер Пенроуз (1990) [1989]. Новый разум императора (2-е изд.). Издательство Оксфордского университета, Нью-Йорк. ISBN 0-19-851973-7.

Малые машины Тьюринга [ править ]

• Рогожин, Юрий, 1998, " Универсальная машина Тьюринга с 22 состояниями и 2 символами ", Румынский журнал информационных наук и технологий , 1 (3), 259–265, 1998. (обзор известных результатов о малых универсальных машинах Тьюринга)
• Стивен Вольфрам , 2002, новый вид науки , Wolfram Media, ISBN 1-57955-008-8 
• Брунфил, Джефф, приз студентов по математике , Nature , 24 октября 2007 г.
• Джим Джайлс (2007 г.), Простейший «универсальный компьютер» приносит студенту 25 000 долларов , New Scientist, 24 октября 2007 г.
• Алекс Смит, Универсальность машины Тьюринга Вольфрама 2, 3 , заявка на соискание премии Wolfram 2, 3 за исследования машины Тьюринга.
• Воан Пратт, 2007, « Простые машины Тьюринга, универсальность, кодировки и т. Д. », Список рассылки FOM. 29 октября 2007 г.
• Мартин Дэвис, 2007, « Самая маленькая универсальная машина » и Определение универсальной машины Тьюринга. Список рассылки FOM. 26–27 октября 2007 г.
• Аласдер Уркхарт, 2007 « Самая маленькая универсальная машина », список рассылки FOM. 26 октября 2007 г.
• Гектор Зенил (Wolfram Research), 2007 « самая маленькая универсальная машина », список рассылки FOM. 29 октября 2007 г.
• Тодд Роуленд, 2007 г., « Путаница по поводу FOM », доска объявлений Wolfram Science, 30 октября 2007 г.
• Оливье и Марк РЭЙНО, 2014 г., Программируемый прототип для создания машин Тьюринга »ЛИМОС Лаборатория Университета Блеза Паскаля (Клермон-Ферран, Франция).

Другое [ править ]

• Мартин Дэвис (2000). Двигатели логики: математики и происхождение компьютера (1-е изд.). WW Norton & Company, Нью-Йорк. ISBN 978-0-393-32229-3.
• Робин Ганди , «Слияние идей в 1936 году», стр. 51–102 в Рольф Херкен , см. Ниже.
• Стивен Хокинг (редактор), 2005, Бог создал целые числа: математические открытия, изменившие историю , Running Press, Филадельфия, ISBN 978-0-7624-1922-7 . Включает статью Тьюринга 1936–1937 годов с кратким комментарием и биографией Тьюринга, написанной Хокингом. 
• Рольф Херкен (1995). Универсальная машина Тьюринга - обзор за полвека . Springer Verlag. ISBN 978-3-211-82637-9.
• Эндрю Ходжес , Алан Тьюринг: Загадка , Саймон и Шустер , Нью-Йорк. Ср. Глава «Дух истины» для истории, ведущей к его доказательству, и его обсуждения.
• Иварс Петерсон (1988). Математический турист: снимки современной математики (1-е изд.). WH Freeman and Company, Нью-Йорк. ISBN 978-0-7167-2064-5.
• Роджер Пенроуз , Новый разум императора: относительно компьютеров, разума и законов физики , Oxford University Press , Оксфорд и Нью-Йорк, 1989 (исправления 1990 г.), ISBN 0-19-851973-7 . 
• Пол Стрэтерн (1997). Тьюринг и компьютер - большая идея . Якорные книги / Doubleday. ISBN 978-0-385-49243-0.
• Хао Ван , «Вариант теории вычислительных машин Тьюринга», Журнал Ассоциации вычислительной техники (JACM) 4, 63–92 (1957).
• Чарльз Петцольд , Петцольд, Чарльз, Аннотированный Тьюринг , John Wiley & Sons, Inc., ISBN 0-470-22905-5 
• Арора, Санджив; Барак, Боаз, «Теория сложности: современный подход» , Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , раздел 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы. 1.9 " 
• Канторовиц, Исайя Пинхас (1 декабря 2005 г.). «Заметка о вычислимости машин Тьюринга для систем, управляемых правилами». Новости SIGACT . 36 (4): 109–110. DOI : 10.1145 / 1107523.1107525 . S2CID  31117713 .
• Кирнер, Раймунд; Циммерманн, Вольф; Рихтер, Дирк: «О результатах неразрешимости реальных языков программирования» , In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Мария Таферль, Австрия, октябрь 2009 г.

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме машин Тьюринга .

• "Машина Тьюринга" , Энциклопедия математики , EMS Press , 2001 [1994]
• Машина Тьюринга в Стэнфордской энциклопедии философии
• Причинные сети машины Тьюринга, автор Энрике Зелени в рамках проекта Wolfram Demonstrations .
• Машины Тьюринга в Керли
• Многоходовые машины Тьюринга от Стивена Вольфрама в рамках бюллетеней проекта Wolfram Physics Project Bulletins