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

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

В информатике универсальная машина Тьюринга ( UTM ) — это машина Тьюринга, способная вычислить любую вычислимую последовательность, как описано Аланом Тьюрингом в его основополагающей статье «О вычислимых числах с применением к проблеме Entscheidungs ». Здравый смысл мог бы сказать, что универсальная машина невозможна, но Тьюринг доказывает, что это возможно. Он предположил, что мы можем сравнить человека в процессе вычисления действительного числа с машиной, которая способна выполнять только конечное число условий . $q_{1},q_{2},\dots ,q_{R}$⁠ ; которые будут называться « m -конфигурации». Затем он описал работу такой машины, как описано ниже, и заявил:

Я утверждаю, что эти операции включают в себя все те операции, которые используются при вычислении числа.

Алан Тьюринг представил идею такой машины в 1936–1937 годах.

Введение

Дополнительная информация: Регистрационная машина § Историческое развитие модели регистровой машины.

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

Дэвис утверждает, что компьютер Тьюринга «Автоматическая вычислительная машина » (ACE) «предвосхитил» понятия микропрограммирования ( микрокода ) и RISC- процессоров. Кнут цитирует работу Тьюринга над компьютером ACE как разработку «аппаратного обеспечения для облегчения связи подпрограмм»; Дэвис также называет эту работу использованием Тьюрингом аппаратного «стека».

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

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

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

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

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

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

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

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

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

Начав с приведенной выше кодировки, в 1966 году Ф. К. Хенни и Р. Э. Стернс показали, что если дана машина Тьюринга M _α , которая останавливается на входе x за N шагов, то существует многоленточная универсальная машина Тьюринга, которая останавливается на входах α , x (заданных на разные ленты) в CN log N , где C — машинная константа, которая не зависит от длины входного сигнала x , но зависит от размера алфавита M , количества лент и количества состояний. По сути, это ${\mathcal {O}}\left(N\log {N}\right)$ моделирование с использованием Дональда Кнута нотации Big O . Соответствующий результат для пространственной сложности, а не для временной сложности, состоит в том, что мы можем моделировать таким образом, чтобы CN . на любом этапе вычислений использовалось не более ячеек ${\mathcal {O}}(N)$ моделирование.

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

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

Марвин Мински открыл универсальную машину Тьюринга с 7 состояниями и 4 символами в 1962 году, используя системы с 2 тегами . Другие небольшие универсальные машины Тьюринга с тех пор были найдены Юрием Рогожиным и другими, расширив этот подход моделирования системы тегов. Если обозначить через ( 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, 0А, 1А, 2А. Рассмотрим ленту типа 0,0,1,2,2A,0,2,1, где трехголовая машина Тьюринга расположена над тройкой (2,2A,0). Затем правила преобразуют любую тройку в другую тройку и перемещают тройку влево или вправо. Например, правила могут преобразовать (2,2A,0) в (2,1,0) и переместить голову влево. Таким образом, в этом примере машина действует как трехцветная машина Тьюринга с внутренними состояниями A и B (не обозначаемыми буквами). Случай с двухголовой машиной Тьюринга очень похож. Таким образом, двухголовая машина Тьюринга может быть универсальной с 6 цветами. Неизвестно, какое наименьшее количество цветов необходимо для многоголовочной машины Тьюринга и возможна ли двухцветная универсальная машина Тьюринга с несколькими головками. Это также означает, что правила перезаписи являются полными по Тьюрингу, поскольку тройные правила эквивалентны правилам перезаписи. Расширяя ленту до двух измерений с головкой, отбирающей букву и ее 8 соседей, потребуется только 2 цвета, например, цвет можно закодировать в вертикальном тройном шаблоне, например 110.

Кроме того, если расстояние между двумя головками является переменным (лента имеет «провисание» между головками), то она может имитировать любую систему тегов Post , некоторые из которых являются универсальными.

Пример кодирования

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

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

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

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

Текущая м-конфигурация	Символ ленты	Операция печати	Лента-движение	Окончательная м-конфигурация	Текущий код m-конфигурации	Код символа ленты	Код операции печати	Код движения ленты	Окончательный код m-конфигурации	5-кортежный ассемблерный код
q1	пустой	Р0	Р	кв2	И	Д	округ Колумбия	Р	ДАА	ДАДДКРДАА
кв2	пустой	И	Р	q3	ДАА	Д	Д	Р	ДААА	ДАДААААААААААААААААА
q3	пустой	П1	Р	q4	ДААА	Д	ДКК	Р	ДА	ДАААДДККРДАААА
q4	пустой	И	Р	q1	ДА	Д	Д	Р	И	НАВОДНЕНИЕ

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

; ДАДДКРДАА ; ПАПОЧКА ; ДААДДККРДААААА ; НАВОДНЕНИЕ

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

э-э. ; .DADDCRDAA ; .ДААДДРДААА ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

э-э. ; .DADDCRDAA ; z Д.АА x Д.ДРДААА ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

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

Роджер Пенроуз приводит примеры способов кодирования инструкций для универсальной машины, используя только двоичные символы { 0, 1 } или { пробел, отметка | }. Пенроуз идет дальше и записывает весь код своей U-машины. Он утверждает, что это действительно U-машинный код, огромное число, занимающее почти две полные страницы, состоящие из единиц и нулей.

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

См. также

• Альтернативная машина Тьюринга – абстрактная модель вычислений
• Счетная машина - абстрактная машина, используемая в формальной логике и теоретической информатике.
• Предикат T Клини - концепция теории вычислимости
• Метка и пробел - состояния сигнала связи
• Эквиваленты машины Тьюринга - Гипотетические вычислительные устройства
• Универсальный конструктор фон Неймана – Самовоспроизводящийся клеточный автомат.

Ссылки

Оригинал статьи и исправления

• Тьюринг, AM (1937). «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) . Труды Лондонского математического общества . 2. 42 (1): 230–265. дои : 10.1112/plms/s2-42.1.230 .
• Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs: исправление». Труды Лондонского математического общества . 2. 43 (6): 544–6. дои : 10.1112/plms/s2-43.6.544 .

Другие цитируемые работы

• Арора, Санджив; Барак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN  978-0-521-42426-4 . раздел 1.4 «Машины как струны и универсальная машина Тьюринга» и 1.7 «Доказательство теоремы 1.9»
• Асперти, Андреа; Риччиотти, Уилмер (2015). «Формализация многоленточных машин Тьюринга». Теоретическая информатика . 603 : 23–42. дои : 10.1016/j.tcs.2015.07.013 . hdl : 11585/536349 . МР   3406235 .
• Беркс, Артур В.; Голдстайн, Герман Х.; фон Нейман, Джон (1971) [1946]. «Планирование и кодирование задач для электронного вычислительного прибора» . В Белле, К. Гордон; Ньюэлл, Аллен (ред.). Компьютерные структуры: материалы для чтения и примеры . Нью-Йорк: Книжная компания McGraw-Hill. стр. 92–119. ISBN  0-07-004357-4 .
• Коупленд, Джек , изд. (2004). Основы Тьюринга: основополагающие труды по информатике, логике, философии, искусственному интеллекту и искусственной жизни, а также «Тайны загадки» . Оксфорд Великобритания: Издательство Оксфордского университета. ISBN  0-19-825079-7 .
• Коупленд, Би Джей; Фан, З. (2023). «Тьюринг и фон Нейман: от логики к компьютеру» . Философии . 8 (22): 22. doi : 10.3390/philosophies8020022 .
• Дэвис, Мартин (1980). «Что такое вычисления?». В Стин, Линн Артур (ред.). Математика сегодня: двенадцать неформальных эссе . Нью-Йорк: Винтажные книги (Random House). ISBN  978-0-394-74503-9 .
• Дэвис, Мартин (2000). Логические машины: математики и происхождение компьютера (1-е изд.). Нью-Йорк: WW Norton & Company. ISBN  0-393-32229-7 .
• Хенни, ФК; Стернс, RE (1966). «Двухленточное моделирование многоленточных машин Тьюринга». Журнал АКМ . 13 (4): 533. дои : 10.1145/321356.321362 . S2CID   2347143 .
• Кнут, Дональд Э. (1973). Искусство компьютерного программирования . Том. 1: Фундаментальные алгоритмы (второе изд.). Издательство Аддисон-Уэсли.
• Кудлек, Манфред; Рогожин, Юрий (2002). «Универсальная машина Тьюринга с 3 состояниями и 9 символами». В Куиче, Вернер; Розенберг, Гжегож; Саломаа, Арто (ред.). Развитие теории языка: 5-я Международная конференция, DLT 2001, Вена, Австрия, 16–21 июля 2001 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 2295. Спрингер. стр. 311–318. дои : 10.1007/3-540-46011-x_27 . ISBN  978-3-540-43453-5 .
• Мински, Марвин Ли (1967). Вычисления: конечные и бесконечные машины . Прентис Холл. ISBN  978-0-13-165563-8 .
• Нири, Терлоу; Вудс, Дэмиен (2009). «Четыре малых универсальных машины Тьюринга» (PDF) . Фундамента информатики . 91 (1): 123–144. дои : 10.3233/FI-2009-0036 .
• Нири, Терлоу; Вудс, Дэмиен (2009b). «Маленькие слабоуниверсальные машины Тьюринга». 17-й Международный симпозиум по основам теории вычислений . Конспекты лекций по информатике. Том. 5699. Спрингер. стр. 262–273.
• Пенроуз, Роджер (1989). Новый разум императора . Оксфорд Великобритания: Издательство Оксфордского университета. ISBN  0-19-851973-7 .
• Рогожин, Юрий (1996). «Маленькие универсальные машины Тьюринга» . Теоретическая информатика . 168 (2): 215–240. дои : 10.1016/S0304-3975(96)00077-1 .

Дальнейшее чтение

• Арбиб, Массачусетс (1988). «От универсальных машин Тьюринга к самовоспроизведению». В Херкен, Р. (ред.). Обзор универсальной машины Тьюринга за полвека . Издательство Оксфордского университета. стр. 177–189. ISBN  978-0-19-853741-0 .
• Дэвис, Мартин, изд. (1965). Неразрешимое . Хьюлетт, Нью-Йорк: Raven Press.
• Дэвис, Мартин (2018). Универсальный компьютер: путь от Лейбница к Тьюрингу . Группа Тейлор и Фрэнсис. ISBN  978-1138413931 .
• Херкен, Рольф (1995). Универсальная машина Тьюринга: обзор полувека . Спрингер Верлаг. ISBN  3-211-82637-8 .
• Мински, Марвин (1962). «Размер и структура универсальных машин Тьюринга, использующих системы тегов, теория рекурсивных функций» . Учеб. Симп. Чистая математика . 5 . Провиденс, Р.И.: Американское математическое общество: 229–238. дои : 10.1090/pspum/005/0142452 .
• Шеннон, Клод (1956). «Универсальная машина Тьюринга с двумя внутренними состояниями». Исследования автоматов . Принстон, Нью-Джерси: Издательство Принстонского университета. стр. 157–165.

Внешние ссылки

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