Машина Тьюринга - Turing machine

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

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

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

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

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

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

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

Обзор

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

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

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

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

Физическое описание

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

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

Описание

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

Голова всегда находится над определенным квадратом ленты; показан только конечный участок квадратов. Инструкция, которую нужно выполнить (q₄) отображается над отсканированным квадратом. (Рисунок по Клини (1952), с. 375.)

Здесь внутреннее состояние (q₁) показан внутри головки, а на иллюстрации лента изображена как бесконечная и предварительно заполнена цифрой «0», символ которой является пустым. Полное состояние системы (ее «полная конфигурация») состоит из внутреннего состояния, любых непустых символов на ленте (на этом рисунке «11B») и положения головки относительно этих символов, включая пробелы, т.е. «011B ". (Рисунок по Минскому (1967), с. 121.)

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

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

Сотрите или напишите символ (заменив_j с_j1).
Переместите голову (что описывается буквой d_k и может иметь значения: 'L' на один шаг влево или же 'R' на шаг вправо или же 'N' - оставаться на одном месте).
Предположим то же самое или новое состояние как предписано (перейти в состояние q_i1).

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

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

Формальное определение

Следующий Хопкрофт и Ульман (1979, п. 148), (однополосную) машину Тьюринга можно формально определить как 7-кортеж ${ 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 - сдвиг вправо. Если ${ displaystyle delta}$ не определен для текущего состояния и текущего символа ленты, машина останавливается;^[22]

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

Относительно необычный вариант позволяет "без сдвига", скажем, 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}$ .

Таблица состояний для занятого бобра с 3 состояниями и 2 символами
Лента символ	Текущее состояние A			Текущее состояние B			Текущее состояние C
Лента символ	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние
0	1	р	B	1	L	А	1	L	B
1	1	L	C	1	р	B	1	р	HALT

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

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

Например,

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

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

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

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

(определение 1): (q_я, S_j, S_k/ E / N, L / R / N, q_м)

( Текущее состояние q_я , отсканированный символ S_j , символ печати S_k/стереть E/никто N , move_tape_one_square влево L/верно р/никто N , новое состояние q_м )

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

(определение 2): (q_я, S_j, q_м, S_k/ E / N, L / R / N)

( Текущее состояние q_я , отсканированный символ S_j , новое состояние q_м , символ печати S_k/стереть E/никто N , move_tape_one_square влево L/верно р/никто N )

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

Пример: таблица состояний для занятого бобра с 3 состояниями, 2 символа, сокращена до 5 кортежей
Текущее состояние	Отсканированный символ	Символ печати	Переместить ленту	Конечное (то есть следующее) состояние	5-кортежи
А	0	1	р	B	(А, 0, 1, R, B)
А	1	1	L	C	(А, 1, 1, Л, C)
B	0	1	L	А	(B, 0, 1, L, А)
B	1	1	р	B	(B, 1, 1, Р, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	ЧАС	(C, 1, 1, N, ЧАС)

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

	Текущая м-конфигурация (Состояние Тьюринга)	Лента символ	Печать-операция	Лента-движение	Окончательная м-конфигурация (Состояние Тьюринга)	5-кратный	5-кратный комментарий	4-кратный
N1	q_я	S_j	Печать (S_k)	Левый L	q_м	(q_я, S_j, S_k, L, q_м)	"blank" = S₀, 1 = S₁, так далее.
N2	q_я	S_j	Печать (S_k)	Правый R	q_м	(q_я, S_j, S_k, R, q_м)	"blank" = S₀, 1 = S₁, так далее.
N3	q_я	S_j	Печать (S_k)	Нет N	q_м	(q_я, S_j, S_k, N, q_м)	"blank" = S₀, 1 = S₁, так далее.	(q_я, S_j, S_k, q_м)
4	q_я	S_j	Нет N	Левый L	q_м	(q_я, S_j, N, L, q_м)		(q_я, S_j, L, q_м)
5	q_я	S_j	Нет N	Правый R	q_м	(q_я, S_j, N, R, q_м)		(q_я, S_j, R, q_м)
6	q_я	S_j	Нет N	Нет N	q_м	(q_я, S_j, N, N, q_м)	Прямой «прыжок»	(q_я, S_j, N, q_м)
7	q_я	S_j	Стереть	Левый L	q_м	(q_я, S_j, E, L, q_м)
8	q_я	S_j	Стереть	Правый R	q_м	(q_я, S_j, E, R, q_м)
9	q_я	S_j	Стереть	Нет N	q_м	(q_я, S_j, E, N, q_м)		(q_я, S_j, E, q_м)

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

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

Штат"

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

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

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

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

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

1А1

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

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

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

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

Таблица для занятого бобра с 3 состояниями ("P" = печать / запись "1")
Лента символ	Текущее состояние A			Текущее состояние B			Текущее состояние C
	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние
0	п	р	B	п	L	А	п	L	B
1	п	L	C	п	р	B	п	р	HALT

Машина Тьюринга "занятого бобра с 3 состояниями" в представление в конечном состоянии. Каждый кружок представляет «состояние» таблицы - «m-конфигурацию» или «инструкцию». «Направление» государства переход показан стрелкой. Ярлык (например, 0 / P, R) рядом с исходящим состоянием (в «хвосте» стрелки) указывает отсканированный символ, который вызывает конкретный переход (например, 0), за которым следует косая черта /, с последующим "поведением" машины, например "п пrint "затем переместить ленту"р рight ». Общепринятого формата не существует. Показанное соглашение взято из Маккласки (1965), Бута (1967), Хилла и Петерсона (1974).

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

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

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

Эволюция вычислений занятого бобра начинается сверху и продолжается до низа.

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

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

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

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

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

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

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

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

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

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

Выбор c-машин, oracle o-машин

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

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

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

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

An машина оракула или o-машина - это а-машина Тьюринга, которая приостанавливает свои вычисления в состоянии "о«в то время как, чтобы завершить свои вычисления, он« ожидает решения »« оракула »- неопределенной сущности», не говоря уже о том, что он не может быть машиной »(Turing (1939), Неразрешимый, п. 166–168).

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

Реализация машины Тьюринга

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

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

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

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

С точки зрения вычислительная сложность, многоленточная универсальная машина Тьюринга должна быть медленнее только на логарифмический фактор по сравнению с машинами, которые он имитирует. Этот результат был получен в 1966 г. Ф. К. Хенни и Р. Э. Стернс. (Арора, Барак, 2009, теорема 1.9)

Сравнение с реальными машинами

Реализация машины Тьюринга с использованием конструктор Лего шт

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

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

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

Экспериментальный прототип машины Тьюринга

Ограничения машин Тьюринга

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

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

Параллелизм

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

Взаимодействие

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

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

История

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

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

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

Что все процессы разработки и анализа теперь могут выполняться механизмами..
— (курсив Бэббиджа, цит. по Ганди, стр. 54)

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

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

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

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

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

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

10. Определение разрешимости диофантова уравнения.. Учитывая Диофантово уравнение с любым количеством неизвестных величин и с рациональными интегральными коэффициентами: разработать процесс, в соответствии с которым за конечное число операций можно определить, разрешимо ли уравнение в целых рациональных числах. Entscheidungsproblem [проблема решения для логика первого порядка ] решается, когда мы знаем процедуру, которая позволяет любому заданному логическому выражению определить с помощью конечного числа операций его достоверность или выполнимость ... Проблему Entscheidungs следует рассматривать как главную проблему математической логики.
— цитируется с этим переводом и оригиналом на немецком языке в 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) в Неразрешимый, п. 160

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

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

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

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

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

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

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

В зависимости от объектов, которыми нравится манипулировать в вычислениях (чисел, таких как неотрицательные целые числа или буквенно-цифровые строки), две модели заняли доминирующее положение в теории сложности, основанной на машинах:
автономная многоленточная машина Тьюринга..., который представляет собой стандартную модель для строковых вычислений, и машина с произвольным доступом (RAM) представленный Куком и Рекхоу ..., который моделирует идеализированный компьютер в стиле фон Неймана.
— ван Эмде Боас 1990: 4

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

Смотрите также

Арифметическая иерархия
Бекенштейн связан, показывая невозможность бесконечных машин Тьюринга конечных размеров и ограниченной энергии
BlooP и FlooP
Занятый бобер
Постоянная Чайтина или же Омега (информатика) для получения информации о проблеме остановки
Китайская комната
Игра жизни Конвея, полный по Тьюрингу клеточный автомат
Цифровая бесконечность
Новый разум императора
Счетчик (по теоретической информатике)
Genetix
Гедель, Эшер, Бах: вечная золотая коса, известная книга, в которой обсуждается, среди прочего, тезис Черча – Тьюринга
Проблема с остановкой, для получения дополнительных ссылок
Гарвардская архитектура
Императивное программирование
Муравей Лэнгтона и Турмиты, простые двумерные аналоги машины Тьюринга
Список вещей, названных в честь Алана Тьюринга
Измененная архитектура Гарварда
Вероятностная машина Тьюринга
Машина Тьюринга с произвольным доступом
Квантовая машина Тьюринга
Клод Шеннон, еще один ведущий мыслитель теории информации
Примеры машины Тьюринга
Переключатель Тьюринга
Брезент Тьюринга, любая вычислительная система или язык, которые, несмотря на полноту Тьюринга, обычно считаются бесполезными для практических вычислений.
Неорганизованная машина, для очень ранних идей Тьюринга о нейронных сетях
Архитектура фон Неймана

Примечания

^ Minsky 1967: 107 «В своей статье 1936 года AM Тьюринг определил класс абстрактных машин, которые теперь носят его имя. Машина Тьюринга - это машина с конечным числом состояний, связанная с особым видом среды - ее лентой, - в которой она может сохранять (а затем восстанавливать) последовательности символов », также Stone 1972: 8, где слово« машина »заключено в кавычки.
^ Stone 1972: 8 утверждает: «Эта« машина »является абстрактной математической моделью», также ср. Sipser 2006: 137ff, описывающий «модель машины Тьюринга». Rogers 1987 (1967): 13 относится к «характеристике Тьюринга», Boolos Burgess и Jeffrey 2002: 25 относится к «особому виду идеализированной машины».
^ Sipser 2006: 137 «Машина Тьюринга может делать все, что может делать настоящий компьютер».
^ Ср. Сипсер 2002: 137. Кроме того, Rogers 1987 (1967): 13 описывает «бумажную ленту бесконечной длины в обоих направлениях». Минский 1967: 118 утверждает: «Лента считается бесконечной в обоих направлениях». Boolos Burgess и Jeffrey 2002: 25 включают возможность, что «на каждом конце стоит кто-нибудь, чтобы добавить дополнительные пустые квадраты по мере необходимости».
^ Ср. Роджерс 1987 (1967): 13. Другие авторы используют слово «квадрат», например Булос Берджесс Джеффри 2002: 35, Мински 1967: 117, Пенроуз 1989: 37.
^ Это слово используется, например, Дэвис 2000: 151
^ Эта таблица представляет собой алгоритм или «эффективная вычислительная процедура», которая обязательно конечна; см. Penrose 1989: 30ff, Stone 1972: 3ff.
^ Булос Берджесс и Джеффри 2002: 25
^ Boolos Burgess Jeffry 2002: 25 иллюстрируют, как машина движется по ленте. Пенроуз 1989: 36-37 описывает себя как «неудобно» с бесконечной лентой, замечающей, что «может быть трудно переключить!»; он «предпочитает [s] думать о ленте как о представлении некоторой внешней среды, через которую может перемещаться наше конечное устройство», и после наблюдения, что «движение» является удобным способом изображения вещей », а затем предполагает, что« устройство получает все его вход из этой среды.
^ «Также по соглашению одно из состояний выделяется как состояние остановки и получает название HALT» (Stone 1972: 9). Первоначальное описание Тьюринга не включало инструкцию HALT, но он допускал «круговое» условие, «конфигурацию, из которой невозможно движение» (см. Turing 1936 in Неразрешимый 1967: 119); это понятие было добавлено в 1950-е годы; увидеть больше на Проблема с остановкой.
^ Ходжес, Эндрю (2012). Алан Тьюринг: Загадка (Столетие изд.). Princeton University Press. ISBN 978-0-691-15564-7.
^ Идея пришла ему в голову в середине 1935 года (возможно, см. Больше в разделе «История») после того, как он задал вопрос. М. Х. А. Ньюман в своих лекциях: «Был ли определенный метод или, как выразился Ньюман,« механический процесс », который можно было бы применить к математическому утверждению и который дал бы ответ, доказуемо ли оно» (Hodges 1983: 93). Тьюринг представил свою работу 31 мая 1936 г. в Лондонское математическое общество для ознакомления с ней. Труды (ср. Hodges 1983: 112), но он был опубликован в начале 1937 г., а оттиски были доступны в феврале 1937 г. (ср. Hodges 1983: 129).
^ См. Сноску в Davis 2000: 151.
^ Тьюринг 1936 г. Неразрешимый 1965: 132–134; Определение «кругового», данное Тьюрингом, можно найти на странице 119.
^ Тьюринг, Алан Мэтисон (1937). "О вычислимых числах в приложении к Entscheidungsproblem". Труды Лондонского математического общества, серия 2. 42 (1): 230–265. Дои:10.1112 / плмс / с2-42.1.230. - Перепечатка: Тьюринг, Алан. «О вычислимых числах в приложении к Entscheidungsproblem». Цифровой архив Тьюринга. Получено 9 июля 2020.
^ Тьюринг 1936 г. Неразрешимый 1965:145
^ Sipser 2006: 137 отмечает, что «машина Тьюринга может делать все, что может делать настоящий компьютер. Тем не менее, даже машина Тьюринга не может решить определенные проблемы. В самом реальном смысле эти проблемы выходят за теоретические пределы вычислений».
^ См. Определение "подач " на Викисловарь
^ ЯВЛЯЮСЬ. Тьюринг (1948). «Интеллектуальные машины (рукопись)». Архив Тьюринга. п. 3.
^ Иногда называют таблица действий или же функция перехода.
^ Обычно пятерки [5-кортежи]: q_яа_j→ q_i1а_j1d_k, но иногда и четверные [четырехкортежные].
^ стр.149; в частности, Хопкрофт и Ульман предполагают, что ${ displaystyle delta}$ не определено для всех состояний из ${ displaystyle F}$

внешняя ссылка

«Машина Тьюринга», Энциклопедия математики, EMS Press, 2001 [1994]
Машина Тьюринга в Стэнфордская энциклопедия философии
Причинные сети машины Тьюринга Энрике Зелени в рамках Вольфрам Демонстрационный проект.
Машины Тьюринга в Керли

[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. Другие авторы используют слово «квадрат», например Булос Берджесс Джеффри 2002: 35, Мински 1967: 117, Пенроуз 1989: 37.

[6] Это слово используется, например, Дэвис 2000: 151

[7] Эта таблица представляет собой алгоритм или «эффективная вычислительная процедура», которая обязательно конечна; см. Penrose 1989: 30ff, Stone 1972: 3ff.

[8] Булос Берджесс и Джеффри 2002: 25

[9] Boolos Burgess Jeffry 2002: 25 иллюстрируют, как машина движется по ленте. Пенроуз 1989: 36-37 описывает себя как «неудобно» с бесконечной лентой, замечающей, что «может быть трудно переключить!»; он «предпочитает [s] думать о ленте как о представлении некоторой внешней среды, через которую может перемещаться наше конечное устройство», и после наблюдения, что «движение» является удобным способом изображения вещей », а затем предполагает, что« устройство получает все его вход из этой среды.

[10] «Также по соглашению одно из состояний выделяется как состояние остановки и получает название HALT» (Stone 1972: 9). Первоначальное описание Тьюринга не включало инструкцию HALT, но он допускал «круговое» условие, «конфигурацию, из которой невозможно движение» (см. Turing 1936 in Неразрешимый 1967: 119); это понятие было добавлено в 1950-е годы; увидеть больше на Проблема с остановкой.

[Hodges-2012-11] Ходжес, Эндрю (2012). Алан Тьюринг: Загадка (Столетие изд.). Princeton University Press. 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 г. Неразрешимый 1965: 132–134; Определение «кругового», данное Тьюрингом, можно найти на странице 119.

[15] Тьюринг, Алан Мэтисон (1937). "О вычислимых числах в приложении к Entscheidungsproblem". Труды Лондонского математического общества, серия 2. 42 (1): 230–265. Дои:10.1112 / плмс / с2-42.1.230. - Перепечатка: Тьюринг, Алан. «О вычислимых числах в приложении к Entscheidungsproblem». Цифровой архив Тьюринга. Получено 9 июля 2020.

[16] Тьюринг 1936 г. Неразрешимый 1965:145

[17] Sipser 2006: 137 отмечает, что «машина Тьюринга может делать все, что может делать настоящий компьютер. Тем не менее, даже машина Тьюринга не может решить определенные проблемы. В самом реальном смысле эти проблемы выходят за теоретические пределы вычислений».

[18] См. Определение "подач " на Викисловарь

[19] ЯВЛЯЮСЬ. Тьюринг (1948). «Интеллектуальные машины (рукопись)». Архив Тьюринга. п. 3.

[20] Иногда называют таблица действий или же функция перехода.

[21] Обычно пятерки [5-кортежи]: q_яа_j→ q_i1а_j1d_k, но иногда и четверные [четырехкортежные].

[22] стр.149; в частности, Хопкрофт и Ульман предполагают, что ${ displaystyle delta}$ не определено для всех состояний из ${ displaystyle F}$

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]