Универсальная машина Тьюринга - Universal Turing machine

В Информатика, а универсальная машина Тьюринга (UTM) это Машина Тьюринга который имитирует произвольную машину Тьюринга на произвольном входе. Универсальная машина, по сути, достигает этого, читая как описание машины, которая будет моделироваться, так и входные данные для этой машины со своей собственной ленты. Алан Тьюринг представил идею такой машины в 1936–1937 гг. Этот принцип считается источником идеи компьютер с хранимой программой использован Джон фон Нейман в 1946 году за «Электронный вычислительный прибор», который теперь носит имя фон Неймана: фон Неймана архитектура.^[1]

С точки зрения вычислительная сложность, многоленточной универсальной машине Тьюринга достаточно быть медленнее к логарифмический фактор по сравнению с машинами, которые он имитирует.^[2]

Вступление

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

«Можно изобрести единственную машину, которую можно использовать для вычисления любой вычислимой последовательности. Если эта машина U поставляется с лентой, в начале которой написано С.Д. [«стандартное описание» таблицы действий] некоторой вычислительной машины M, тогда U вычислит ту же последовательность, что и M."^[3]

Компьютер с хранимой программой

Дэвис приводит убедительный аргумент, что концепция Тьюринга о том, что сейчас известно как «компьютер с хранимой программой», о размещении «таблицы действий» - инструкций для машины - в той же «памяти», что и входные данные, сильно повлияла на Джон фон Нейман концепция первого американского компьютера с дискретными символами (в отличие от аналогового) - EDVAC. Цитаты Дэвиса Время журнал о том, что «каждый, кто стучит по клавиатуре ... работает над воплощением машины Тьюринга», и что «Джон фон Нейман [построил] на работе Алана Тьюринга» (Davis 2000: 193, цитируя Время журнал от 29 марта 1999 г.).

Дэвис утверждает, что Тьюринг Автоматическая вычислительная машина (ACE) компьютер «предвосхитил» представления о микропрограммировании (микрокод ) и RISC процессоры (Дэвис 2000: 188). Knuth цитирует работу Тьюринга над компьютером ACE как разработку «оборудования для облегчения связи подпрограмм» (Knuth 1973: 225); Дэвис также ссылается на эту работу как на использование Тьюрингом аппаратного «стека» (Davis 2000: 237, сноска 18).

Поскольку машина Тьюринга поощряла создание компьютеры, UTM поощрял развитие молодых компьютерные науки. Ранний, если не самый первый, ассемблер был предложен «молодым опытным программистом» для EDVAC (Davis 2000: 192). «Первая серьезная программа фон Неймана ... [заключалась] в простой эффективной сортировке данных» (Davis 2000: 184). Кнут отмечает, что возврат подпрограммы, встроенный в саму программу, а не в специальные регистры, принадлежит фон Нейману и Голдстайну.^[4] Кнут далее заявляет, что

«Первой интерпретирующей программой можно назвать« универсальную машину Тьюринга »... Интерпретативные процедуры в общепринятом смысле были упомянуты Джоном Мочли в его лекциях в школе Мура в 1946 году ... Тьюринг также принимал участие в этой разработке; интерпретирующие системы для компьютера Pilot ACE были написаны под его руководством »(Knuth 1973: 226).

Дэвис кратко упоминает операционные системы и компиляторы как результат концепции программы как данных (Davis 2000: 185).

Однако у некоторых могут возникнуть проблемы с этой оценкой. В то время (с середины 1940-х до середины 1950-х) относительно небольшая группа исследователей была тесно связана с архитектурой новых «цифровых компьютеров». Хао Ван (1954), молодой исследователь того времени, сделал следующее наблюдение:

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

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

Что касается сведения компьютеров к простым эквивалентным моделям Тьюринга (и наоборот), то определение Мински Ванга как создателя «первой формулировки» открыто для обсуждения. Хотя работа Мински 1961 года и статья Ванга 1957 года цитируются Шепердсоном и Стерджисом (1963), они также цитируют и обобщают некоторые детали работы европейских математиков Кафенста (1959), Ершова (1959) и Петера (1958). Имена математиков Гермеса (1954, 1955, 1961) и Кафенста (1959) появляются в библиографиях Шепердсона-Стерджиса (1963) и Элгот-Робинсона (1961). Два других важных имени - это канадские исследователи Мелзак (1961) и Ламбек (1961). Подробнее см. Эквиваленты машины Тьюринга; ссылки можно найти на зарегистрировать машину.

Математическая теория

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

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

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

Эффективность

Без потери общности можно считать, что вход машины Тьюринга находится в алфавите {0, 1}; любой другой конечный алфавит можно закодировать с помощью {0, 1}. Поведение машины Тьюринга M определяется его переходной функцией. Эту функцию также можно легко закодировать как строку в алфавите {0, 1}. Размер алфавита M, количество имеющихся лент и размер пространства состояний можно определить из таблицы функции перехода. Выделенные состояния и символы можно идентифицировать по их положению, например первые два состояния по соглашению могут быть состояниями запуска и остановки. Следовательно, любую машину Тьюринга можно закодировать как строку в алфавите {0, 1}. Кроме того, мы отмечаем, что каждая недопустимая кодировка отображается на тривиальную машину Тьюринга, которая немедленно останавливается, и что каждая машина Тьюринга может иметь бесконечное количество кодировок, дополняя кодировку произвольным числом (скажем) единиц в конце, точно так же, как комментарии работать на языке программирования. Неудивительно, что мы можем добиться такого кодирования, учитывая наличие Число Гёделя и вычислительная эквивалентность между машинами Тьюринга и μ-рекурсивные функции. Точно так же наша конструкция ассоциируется с каждой двоичной строкой α, машина Тьюринга M_α.

Исходя из приведенной выше кодировки, в 1966 г. F. C. Hennie и Р. Э. Стернс показал, что с учетом машины Тьюринга M_α который останавливается при вводе Икс в N шагов, то существует многоленточная универсальная машина Тьюринга, которая останавливается на вводе α, Икс (даны на разных кассетах) в CN бревно N, куда C - машинно-зависимая константа, не зависящая от длины ввода. Икс, но зависит от М 's размер алфавита, количество лент и количество состояний. Фактически это ${ displaystyle { mathcal {O}} left (N log {N} right)}$ моделирование с использованием Дональд Кнут с Обозначение Big O.^[5] Соответствующий результат для пространственной сложности, а не для временной сложности состоит в том, что мы можем моделировать способом, который использует не более CN ячеек на любом этапе вычислений, ${ Displaystyle { mathcal {O}} (N)}$ моделирование.^[6]

Самые маленькие машины

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

Марвин Мински открыл универсальную машину Тьюринга с 7 состояниями и 4 символами в 1962 году, используя 2-теговые системы. Другие небольшие универсальные машины Тьюринга были с тех пор найдены Юрий Рогожин и другие, расширив этот подход моделирования системы тегов. Если обозначить через (м, п) класс UTM с м государства и п символов найдены следующие кортежи: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) и (2, 18) .^[7]^[8]^[9] Машина Рогожина (4, 6) использует всего 22 инструкции, и не известно ни одного стандартного UTM с меньшей описательной сложностью.

Однако обобщение стандартной модели машины Тьюринга допускает еще меньшие UTM. Одно из таких обобщений состоит в том, чтобы разрешить бесконечно повторяющееся слово на одной или обеих сторонах входа машины Тьюринга, таким образом расширяя определение универсальности и известное как «полуслабая» или «слабая» универсальность соответственно. Небольшие слабо универсальные машины Тьюринга, моделирующие Правило 110 клеточный автомат был дан для пар состояние-символ (6, 2), (3, 3) и (2, 4).^[10] Доказательство универсальности Машина Тьюринга с 2 состояниями и 3 символами Вольфрама далее расширяет понятие слабой универсальности, допуская некоторые непериодические начальные конфигурации. Другие варианты стандартной модели машины Тьюринга, которые дают небольшие UTM, включают машины с несколькими лентами или лентами нескольких размеров, а также машины, соединенные с конечный автомат.

Машины без внутренних состояний

Если вы разрешите использование нескольких головок на машине Тьюринга, тогда у вас может быть машина Тьюринга без внутренних состояний вообще. «Состояния» кодируются как часть ленты. Например, рассмотрим ленту с 6 цветами: 0, 1, 2, 0A, 1A, 2A. Рассмотрим ленту типа 0,0,1,2,2A, 0,2,1, на которой трехголовая машина Тьюринга расположена над тройкой (2,2A, 0). Затем правила конвертируют любую тройку в другую тройку и перемещают тройку влево или вправо. Например, правила могут преобразовывать (2,2A, 0) в (2,1,0) и перемещать голову влево. Таким образом, в этом примере машина действует как трехцветная машина Тьюринга с внутренними состояниями A и B (обозначенными без буквы). Случай с двухголовой машиной Тьюринга очень похож. Таким образом, двухголовая машина Тьюринга может быть универсальной с 6 цветами. Неизвестно, какое наименьшее количество цветов необходимо для многоголовой машины Тьюринга и возможна ли двухцветная универсальная машина Тьюринга с несколькими головками. Это также означает, что переписать правила полны по Тьюрингу, поскольку тройные правила эквивалентны правилам перезаписи. Если расширить ленту до двух измерений с помощью головки, отбирающей букву и ее 8 соседей, необходимо только 2 цвета, например, цвет может быть закодирован в вертикальном тройном шаблоне, таком как 110.

Пример универсального машинного кодирования

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

Следующий пример взят из работы Тьюринга (1936). Подробнее об этом примере см. На странице Примеры машины Тьюринга.

Тьюринг использовал семь символов {A, C, D, R, L, N,; } для кодирования каждого кортежа из пяти; как описано в статье Машина Тьюринга, его 5-кортежи относятся только к типам N1, N2 и N3. Номер каждой «m-конфигурации» (инструкция, состояние) представлен буквой «D», за которой следует унарная строка из A, например «q3» = DAAA. Аналогичным образом он кодирует пустые символы как «D», символ «0» как «DC», символ «1» как DCC и т. Д. Символы «R», «L» и «N» остаются как является.

После кодирования каждый кортеж из 5 элементов затем «собирается» в строку в порядке, показанном в следующей таблице:

Текущая м-конфигурация	Лента символ	Печать-операция	Лента-движение	Окончательная м-конфигурация	Текущий код m-конфигурации	Код символа ленты	Код операции печати	Код движения ленты	Окончательный код m-конфигурации	5-кратный ассемблерный код

q1	пустой	P0	р	q2	DA	D	ОКРУГ КОЛУМБИЯ	р	DAA	DADDCRDAA
q2	пустой	E	р	q3	DAA	D	D	р	DAAA	DAADDRDAAA
q3	пустой	P1	р	q4	DAAA	D	DCC	р	DAAAA	DAAADDCCRDAAAA
q4	пустой	E	р	q1	DAAAA	D	D	р	DA	DAAAADDRDA

Наконец, коды для всех четырех 5-кортежей объединяются в код, начинающийся с ";" и разделены ";" то есть:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

Этот код он поместил в альтернативные квадраты - «F-квадраты», оставив «E-квадраты» (те, которые могут быть удалены) пустыми. Окончательная сборка кода на ленте для U-машины состоит из размещения двух специальных символов («e») один за другим, затем кода, разделенного на чередующиеся квадраты, и, наконец, символа двойного двоеточия "::"(пробелы показаны здесь с". "для ясности):

ее.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

Таблица действий U-машины (таблица переходов между состояниями) отвечает за декодирование символов. Таблица действий Тьюринга отслеживает свое место с помощью маркеров «u», «v», «x», «y», «z», помещая их в «E-квадраты» справа от «отмеченного символа» - например , чтобы отметить текущую инструкцию z помещается справа от ";" Икс сохраняет место по отношению к текущему DAA "m-конфигурации". Таблица действий U-машины будет перемещать эти символы (стирая их и помещая в разные места) по мере выполнения вычислений:

ее.; .D.A.D.D.C.R.D.A.A. ; zD.A.AИксD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

Таблица действий Тьюринга для его U-машины очень сложна.

Ряд других комментаторов (особенно Пенроуз 1989 ) предоставляют примеры способов кодирования инструкций для универсальной машины. Как и Пенроуз, большинство комментаторов используют только двоичные символы, т.е. только символы {0, 1} или {blank, mark | }. Пенроуз идет дальше и записывает весь свой код U-машины (Penrose 1989: 71–73). Он утверждает, что это действительно U-машинный код, огромное число, занимающее почти 2 полные страницы, состоящие из единиц и нулей. Для читателей, интересующихся более простыми кодировками для Машина Пост-Тьюринга обсуждение Дэвиса в Стин (Steen 1980: 251ff) может быть полезным.

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

Программирование машин Тьюринга

Различные языки более высокого уровня предназначены для компиляции в машину Тьюринга. Примеры включают Лаконичный и дескриптор машины Тьюринга.^[11]^[12]

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

Переменная машина Тьюринга
Универсальный конструктор фон Неймана - попытка построить самовоспроизводящуюся машину Тьюринга
T-предикат Клини - аналогичная концепция для µ-рекурсивных функций
Полнота по Тьюрингу

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

Смит, Элви Рэй. «Универсальная машина Тьюринга для визитных карточек» (PDF). Получено 2 января 2020.

[Davis-1] Мартин Дэвис, Универсальный компьютер: путь от Лейбница к Тьюрингу (2017)

[2] Арора, Барак, 2009, теорема 1.9

[3] Жирный шрифт заменяющий. Тьюринг 1936 в Дэвисе 1965: 127–128. В конце статьи приведен пример представления Тьюринга о С.Д.

[4] В частности: Беркс, Голдстайн, фон Нейман (1946), Предварительное обсуждение логической конструкции электронного вычислительного прибора., перепечатано в Bell and Newell 1971 г.

[5] Арора, Барак, 2009, теорема 1.9

[6] Арора и Барак, 2009 г., Упражнения 4.1.

[7] Рогожин, 1996 г.

[8] Кудлек, Рогожин, 2002 г.

[9] Нари и Вудс, 2009

[10] Нири и Вудс, 2009b

[11] «Shtetl-Optimized» Архив блога »8000-е число занятых бобров ускользает от теории множеств ZF: новая статья Адама Йедидиа и меня». www.scottaaronson.com. Получено 29 декабря 2016.

[12] «Лаконичный - Эсоланг». esolangs.org. Получено 29 декабря 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]