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

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

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

Введение [ править ]

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

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

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

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

Дэвис утверждает, что компьютер Turing Automatic Computing Engine (ACE) «предвосхитил» идеи микропрограммирования ( микрокода ) и процессоров RISC (Davis 2000: 188). Кнут цитирует работу Тьюринга над компьютером 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 году Ф. К. Хенни и Р. Р. Стернс показали, что для машины Тьюринга M _α, которая останавливается на входе x в течение N шагов, тогда существует многоленточная универсальная машина Тьюринга, которая останавливается на входах α , x (приведенных на различных лент) в CN log N , где C - машинно-зависимая константа, которая не зависит от длины входного x , но зависит от размера алфавита M , количества лент и количества состояний. Эффективно это моделирование, используя Дональда Кнута «S${\ displaystyle {\ mathcal {O}} \ left (N \ log {N} \ right)}$Big O нотации . ^[5] Соответствующий результат для пространственной сложности, а не временной сложности состоит в том, что мы можем моделировать таким образом, чтобы использовать максимум CN ячеек на любом этапе вычислений, моделирования. ^[6]${\ Displaystyle {\ 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). ^{[7] [8] [9]} Машина Рогожина (4, 6) использует всего 22 инструкции, и не известно ни одного стандартного UTM с меньшей описательной сложностью.

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

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

; DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA

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

ее. ; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

ее. ; .DADDCRDAA ; z D.AA x D.DRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

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

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

Программирование машин Тьюринга [ править ]

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

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

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

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

Общие ссылки

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

Оригинальная бумага

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

Семинары

• Хенни, ФК; Стернс, Р. Э. (1966). «Двухленточное моделирование многоленточных машин Тьюринга». Журнал ACM . 13 (4): 533. DOI : 10,1145 / 321356,321362 . S2CID  2347143 .

Выполнение

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

Формальная проверка

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

Прочие ссылки

• Коупленд, Джек , изд. (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). Компьютерные структуры: чтения и примеры (переиздание ред.). Нью-Йорк: Книжная компания McGraw-Hill. С.  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, pp. 311–318, doi : 10.1007 / 3-540-46011-x_27 , ISBN 978-3-540-43453-5
• Минский, Марвин (1962), "Размер и структура универсальных машин Тьюринга с использованием систем тегов, теории рекурсивных функций", Proc. Symp. Чистая математика , Providence RI: Американское математическое общество, 5 : 229-238, DOI : 10,1090 / pspum / 005/0142452
• Нари, Терлаф; Леса, Damien (2009), "Четыре Малая универсальная машина Тьюринга" (PDF) , Fundamenta Informaticae , 91 (1): 123-144, DOI : 10,3233 / FI-2009-0036
• Нари, Терлаф; Вудс, Дэмиен (2009b), «Малые слабо универсальные машины Тьюринга», 17-й Международный симпозиум по основам теории вычислений , конспект лекций по компьютерным наукам, 5699 , Springer, стр. 262–273
• Пенроуз, Роджер (1989), Новый разум императора , Оксфорд, Великобритания: Oxford University Press, ISBN 0-19-851973-7, (hc.), (pb.)
• Рогожин, Юрий (1996), "Малая универсальная машина Тьюринга", Теоретическая информатика , 168 (2): 215-240, DOI : 10.1016 / S0304-3975 (96) 00077-1
• Шеннон, Клод (1956), «Универсальная машина Тьюринга с двумя внутренними состояниями», Исследования автоматов , Принстон, Нью-Джерси: Princeton University Press, стр. 157–165
• Тьюринг AM (1936), «О вычислимых числах в приложении к Entscheidungsproblem», Труды Лондонского математического общества , 2, 42 , стр. 230–65, doi : 10.1112 / plms / s2-42.1.230
• Turing, AM (1938), "О вычислимых числах, с приложением к коррекции: проблема разрешения А", Труды Лондонского математического общества , 2 (опубликовано 1937), 43 (6), стр 544-6,. Дои : 10,1112 /plms/s2-43.6.544) Дэвис Эд, Мартин (1965). Неразрешимое (Перепечатка ред.). Хьюлетт, Нью-Йорк: Raven Press. С. 115–154. с поправками к UTM Тьюринга, сделанными Эмилем Постом, см. сноску 11, стр. 299
  CS1 maint: дополнительный текст: список авторов ( ссылка )

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

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