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

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

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

• 1 Введение
• 2 Компьютер с хранимой программой
• 3 Математическая теория
• 4 Эффективность
• 5 Самые маленькие машины
• 6 Машины без внутренних состояний
• 7 Пример кодирования универсальной машины
• 8 Программирование машин Тьюринга
• 9 См. Также
• 10 Ссылки
• 11 Внешние ссылки

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

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

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

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

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

«Первой программой интерпретации можно назвать« Универсальную машину Тьюринга »... Процедуры интерпретации в общепринятом смысле упоминались Джоном Мочли в его лекциях в Школе Мура в 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). Имена математиков Hermes (1954, 1955, 1961) и Kaphenst (1959) появляются в библиографиях bot h Шепердсон-Стерджис (1963) и Элгот-Робинсон (1961). Два других важных имени - это канадские исследователи Мелзак (1961) и Ламбек (1961). Подробнее см. эквиваленты машины Тьюринга ; ссылки можно найти на регистровой машине.

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

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

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

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

, начиная с приведенной выше кодировки, в 1966 г. F. C. Hennie и R. Э. Стернс показал, что для машины Тьюринга M α, которая останавливается на входе x в течение N шагов, тогда существует многоленточная универсальная машина Тьюринга, которая останавливается на входах α, x (заданных на разных ленты) в CN log N, где C - машинно-зависимая константа, которая не зависит от длины входного x, но зависит от размера алфавита M, количества лент и количества состояний. Фактически это моделирование $O\; (N\; log\; \; N)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{O\}\}\; \backslash \; left\; (N\; \backslash \; log\; \{N\}\; \backslash \; right)\}$с использованием Donald Обозначение Кнута Big O. Соответствующий результат для пространственной сложности, а не временной сложности состоит в том, что мы можем моделировать таким образом, чтобы использовать не более чем CN ячеек на любом этапе вычислений, $O\; (N)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{O\}\; \}\; (N)\}$моделирование.

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

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

Однако обобщение стандартной модели машины Тьюринга допускает даже меньшие UTM. Одно из таких обобщений состоит в том, чтобы разрешить бесконечно повторяющееся слово на одной или обеих сторонах входа машины Тьюринга, таким образом расширяя определение универсальности и известное как «полуслабая» или «слабая» универсальность соответственно. Небольшие слабо универсальные машины Тьюринга, моделирующие клеточный автомат Правило 110, были даны для пар (6, 2), (3, 3) и (2, 4) символ состояния. Доказательство универсальности двухуровневой трехсимвольной машины Тьюринга Вольфрама расширяет понятие слабой универсальности, допуская определенные непериодические начальные конфигурации. Другие варианты стандартной модели машины Тьюринга, которые дают небольшие 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: 103ff). Дэвис исправляет ошибки в оригинале и показывает, как будет выглядеть пробный прогон. Он утверждает, что успешно провел (несколько упрощенное) моделирование.

Следующий пример взят из работы Тьюринга (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 элементов затем «собирается» в строку в порядке, показанном в следующей таблице:

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

;DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA

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

ee. ; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

ee. ; .D.A.D.C.R.D.A.A. ;zDAA x DDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

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

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

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

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

Общие ссылки

• Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход. Издательство Кембриджского университета. ISBN 978-0-521-42426-4. раздел 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9»

Исходная статья

• Тьюринг, А.М. (1936). «О вычислимых числах в приложении к Entscheidungsproblem» (PDF).

Основные документы

• Hennie, F.C.; Стернс, Р. Э. (1966). «Двухленточное моделирование многоленточных машин Тьюринга». Журнал ACM. 13 (4): 533. doi : 10.1145 / 321356.321362.

Реализация

• Kamvysselis (Kellis), Manolis (1999). «Реализация схемы универсальной машины Тьюринга». Самостоятельно опубликовано.

Официальная проверка

• Асперти, Андреа; Риччиотти, Уилмер (2015). «Формализация многоленточных машин Тьюринга» (PDF). Теоретическая информатика. Эльзевир. 603 : 23–42. doi : 10.1016 / j.tcs.2015.07.013. ISSN 0304-3975.

Другие ссылки

• Copeland, Jack, ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford UK: Oxford University Press, ISBN 0-19- 825079-7
• Дэвис, Мартин (1980), «Что такое вычисления?», В Стин, Линн Артур (ред.), Математика сегодня: двенадцать неформальных эссе, Нью-Йорк: Vintage Books (Random House), ISBN 978-0-394-74503-9.
• Дэвис, Мартин (2000), Двигатели логики: математики и происхождение компьютера (1-е изд.), Нью-Йорк, штат Нью-Йорк: WW Norton Company, ISBN 0-393-32229-7, (pb.)
• Goldstine, Herman H.; фон Нейман, Джон. Планирование и кодирование задач для электронного вычислительного прибора. Институт перспективных исследований (изд. 1947 г.). Принстон.. Белл, К. Гордон; Ньюэлл, Аллен (1971). Компьютерные структуры: материалы и примеры (Переиздание). Нью-Йорк: Книжная компания Макгроу-Хилл. С. 92–119. ISBN 0-07-004357-4.
• (1995), Универсальная машина Тьюринга - полувековой обзор, Springer Verlag, ISBN 3- 211-82637-8
• Кнут, Дональд Э.. (1968), Искусство компьютерного программирования, второе издание, том 1 / Фундаментальные алгоритмы (2-е, 1973) | format =требует | url =() (Первое изд.), Addison-Wesley Publishing Company Первый из трех текстов Кнута.
• Кудлек, Манфред; Рогожин, Юрий (2002), «Универсальная машина Тьюринга с 3 состояниями и 9 символами», Вернер Куич; Гжегож Розенберг; Арто Саломаа (ред.), Развитие теории языка: 5-я Международная конференция, DLT 2001 Вена, Австрия, 16–21 июля 2001 г., Revised Papers, Lecture Notes in Computer Science, 2295, Springer, стр. 311–318, doi : 10.1007 / 3-540-46011-x_27, ISBN 978-3-540-43453-5
• Мински, Марвин (1962), "Размер и структура универсальных машин Тьюринга, использующих системы тегов, теория рекурсивных функций", Proc. Symp. Pure Mathematics, Providence RI: Американское математическое общество, 5 : 229–238, doi : 10.1090 / pspum / 005/0142452
• Нири, Терлаф; Вудс, Дэмиен (2009), «Четыре малых универсальных машины Тьюринга», Fundamenta Informaticae, 91 (1)
• Нири, Терлаф; Вудс, Дэмиен (2009b), «Маленькие слабо универсальные машины Тьюринга», 17-й Международный симпозиум по основам теории вычислений, Конспекты лекций по информатике, 5699, Springer, стр. 262– 273
• Пенроуз, Роджер (1989), The Emperor's New Mind, Oxford UK: Oxford University Press, ISBN 0-19-851973-7, (hc.), (Pb.)
• Рогожин, Юрий (1996), "Малые универсальные машины Тьюринга", Теоретическая информатика, 168 (2): 215–240, doi : 10.1016 / S0304-3975 (96) 00077-1
• Шеннон, Клод (1956), «Универсальная машина Тьюринга с двумя внутренними состояниями», Automata Studies, Princeton, NJ : Princeton University Press, стр. 157–165
• Тьюринг, AM (1936), «О вычислимых числах в приложении к Entscheidungsproblem», Proceedings of the London Mathematical Society, 2, 42, pp. 230–65, doi : 10.1112 / плмс / с2-42.1.230
• Тьюринг, AM (1938), «О вычислимых числах в приложении к проблеме Entscheidungs: исправление», Труды Лондонского математического общества, 2 (опубликовано в 1937 году), 43 (6), стр. 544–6, doi : 10.1112 / plms / s2-43.6.544 ). Дэвис, Мартин (1965). Неразрешимое (Переиздание ред.). Хьюлетт, Нью-Йорк: Raven Press. С. 115–154. с исправлениями к UTM Тьюринга, сделанными Эмилем Постом, см. Сноску 11 стр.: 299CS1 maint: дополнительный текст: список авторов (ссылка )

Smith, Alvy Ray. «Универсальная машина Тьюринга для визитных карточек» (PDF). Проверено 2 января 2020 г.