В информатике универсальная машина Тьюринга ( UTM ) — это машина Тьюринга, способная вычислять любую вычислимую последовательность, [1] как описано Аланом Тьюрингом в его основополагающей статье «О вычислимых числах с приложением к проблеме Entscheidungsproblem ». Здравый смысл может сказать, что универсальная машина невозможна, но Тьюринг доказывает, что она возможна. [a] Он предположил, что мы можем сравнить человека в процессе вычисления действительного числа с машиной, которая способна только на конечное число условий ; которые будут называться « m -конфигурациями». [2] Затем он описал работу такой машины, как описано ниже, и утверждал:
Я утверждаю, что эти операции включают все те, которые используются при вычислении числа. [3]
Алан Тьюринг выдвинул идею такой машины в 1936–1937 годах.
Дэвис приводит убедительный аргумент, что концепция Тьюринга того, что сейчас известно как «компьютер с хранимой программой», о размещении «таблицы действий» — инструкций для машины — в той же «памяти», что и входные данные, сильно повлияла на концепцию Джона фон Неймана о первом американском дискретно-символьном (в отличие от аналогового) компьютере — EDVAC . Дэвис цитирует журнал Time в этом смысле, что «каждый, кто стучит по клавиатуре... работает над воплощением машины Тьюринга», и что «Джон фон Нейман [построил] на работе Алана Тьюринга». [4]
Дэвис утверждает, что компьютер Тьюринга Automatic Computing Engine (ACE) «предвосхитил» понятия микропрограммирования ( микрокода ) и RISC- процессоров. [5] Кнут ссылается на работу Тьюринга над компьютером ACE как на разработку «аппаратного обеспечения для облегчения связывания подпрограмм»; [6] Дэвис также ссылается на эту работу как на использование Тьюрингом аппаратного «стека». [7]
В то время как машина Тьюринга способствовала созданию компьютеров , UTM способствовала развитию зарождающихся компьютерных наук . Ранний, если не первый, ассемблер был предложен «молодым амбициозным программистом» для EDVAC. [8] «Первая серьезная программа фон Неймана... [была] простой эффективной сортировкой данных». [9] Кнут замечает, что возврат подпрограммы, встроенный в саму программу, а не в специальные регистры, приписывается фон Нейману и Голдстайну. [b] Кнут далее утверждает, что
Можно сказать, что первой интерпретативной программой была «Универсальная машина Тьюринга»... Интерпретативные программы в общепринятом смысле были упомянуты Джоном Мочли в его лекциях в Школе Мура в 1946 году... Тьюринг также принимал участие в этой разработке; интерпретативные системы для компьютера Pilot ACE были написаны под его руководством. [10]
Дэвис кратко упоминает операционные системы и компиляторы как результаты концепции программы как данных. [11]
С помощью этой кодировки таблиц действий в виде строк, в принципе, становится возможным для машин Тьюринга отвечать на вопросы о поведении других машин Тьюринга. Однако большинство этих вопросов неразрешимы , что означает, что рассматриваемая функция не может быть вычислена механически. Например, проблема определения того, остановится ли произвольная машина Тьюринга на определенном входе или на всех входах, известная как проблема остановки , была показана, в общем случае, неразрешимой в оригинальной статье Тьюринга. Теорема Райса показывает, что любой нетривиальный вопрос о выходе машины Тьюринга неразрешим.
Универсальная машина Тьюринга может вычислить любую рекурсивную функцию , решить любой рекурсивный язык и принять любой рекурсивно перечислимый язык . Согласно тезису Чёрча–Тьюринга , проблемы, решаемые универсальной машиной Тьюринга, — это в точности те проблемы, которые решаются алгоритмом или эффективным методом вычисления , для любого разумного определения этих терминов. По этим причинам универсальная машина Тьюринга служит стандартом, с которым сравниваются вычислительные системы, а система, которая может имитировать универсальную машину Тьюринга, называется полной по Тьюрингу .
Абстрактной версией универсальной машины Тьюринга является универсальная функция , вычислимая функция, которая может быть использована для вычисления любой другой вычислимой функции. Теорема UTM доказывает существование такой функции.
Без потери общности можно предположить, что вход машины Тьюринга находится в алфавите {0, 1}; любой другой конечный алфавит может быть закодирован в {0, 1}. Поведение машины Тьюринга M определяется ее функцией перехода. Эту функцию также можно легко закодировать в виде строки в алфавите {0, 1}. Размер алфавита M , количество лент в нем и размер пространства состояний можно вывести из таблицы функции перехода. Различаемые состояния и символы можно идентифицировать по их положению, например, первые два состояния могут по соглашению быть начальным и конечным состояниями. Следовательно, каждую машину Тьюринга можно закодировать в виде строки в алфавите {0, 1}. Кроме того, мы условимся, что каждое недопустимое кодирование отображается в тривиальную машину Тьюринга, которая немедленно останавливается, и что каждая машина Тьюринга может иметь бесконечное количество кодирований, дополняя кодировку произвольным числом (скажем) единиц в конце, точно так же, как комментарии работают в языке программирования. Неудивительно, что мы можем достичь этого кодирования, учитывая существование числа Гёделя и вычислительной эквивалентности между машинами Тьюринга и μ-рекурсивными функциями . Аналогично, наша конструкция связывает каждую двоичную строку α с машиной Тьюринга M α .
Начиная с вышеприведенной кодировки, в 1966 году FC Hennie и RE Stearns показали, что если задана машина Тьюринга M α , которая останавливается на входе x в течение N шагов, то существует многоленточная универсальная машина Тьюринга, которая останавливается на входах α , x (заданных на разных лентах) в CN log N , где C — константа, специфичная для машины, которая не зависит от длины входа x , но зависит от размера алфавита M , количества лент и количества состояний. По сути, это симуляция с использованием нотации Big O Дональда Кнута . [12] Соответствующий результат для пространственной сложности, а не для временной сложности заключается в том, что мы можем проводить симуляцию таким образом, чтобы использовать не более CN ячеек на любом этапе вычисления, симуляцию. [13]
Когда Алан Тьюринг придумал идею универсальной машины, он имел в виду простейшую вычислительную модель, достаточно мощную для вычисления всех возможных функций, которые можно вычислить. Клод Шеннон впервые явно поставил вопрос о нахождении наименьшей возможной универсальной машины Тьюринга в 1956 году. Он показал, что двух символов достаточно, если используется достаточное количество состояний (или наоборот), и что всегда можно обменять состояния на символы. Он также показал, что не может существовать универсальной машины Тьюринга с одним состоянием.
Марвин Мински открыл 7-состоянную 4-символьную универсальную машину Тьюринга в 1962 году, используя 2-теговые системы . Другие малые универсальные машины Тьюринга были с тех пор найдены Юрием Рогожиным и другими путем расширения этого подхода моделирования системы тегов. Если обозначить через ( m , n ) класс UTM с m состояниями и n символами, то были найдены следующие кортежи: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) и (2, 18). [14] [15] [16] Машина Рогожина (4, 6) использует только 22 инструкции, и не известно ни одного стандартного UTM меньшей описательной сложности.
Однако обобщение стандартной модели машины Тьюринга допускает даже меньшие UTM. Одним из таких обобщений является разрешение бесконечно повторяющегося слова на одной или обеих сторонах входа машины Тьюринга, тем самым расширяя определение универсальности и известное как «полуслабая» или «слабая» универсальность соответственно. Малые слабо универсальные машины Тьюринга, которые имитируют клеточный автомат Правила 110, были даны для пар состояние-символ (6, 2), (3, 3) и (2, 4). [17] Доказательство универсальности для 2-состоянной 3-символьной машины Тьюринга Вольфрама еще больше расширяет понятие слабой универсальности, допуская определенные непериодические начальные конфигурации. Другие варианты стандартной модели машины Тьюринга, которые дают малые UTM, включают машины с несколькими лентами или лентами нескольких измерений, а также машины, соединенные с конечным автоматом .
Если на машине Тьюринга разрешено несколько головок, то внутренние состояния не требуются; поскольку «состояния» могут быть закодированы на ленте. Например, рассмотрим ленту с 6 цветами: 0, 1, 2, 0A, 1A, 2A. Рассмотрим ленту, такую как 0,0,1,2,2A,0,2,1, где 3-головая машина Тьюринга расположена над тройкой (2,2A,0). Затем правила преобразуют любую тройку в другую тройку и перемещают 3-головки влево или вправо. Например, правила могут преобразовать (2,2A,0) в (2,1,0) и перемещать головку влево. Таким образом, в этом примере машина действует как 3-цветная машина Тьюринга с внутренними состояниями A и B (обозначенными без буквы). Случай для 2-головой машины Тьюринга очень похож. Таким образом, 2-головая машина Тьюринга может быть универсальной с 6 цветами. Неизвестно, каково наименьшее количество цветов, необходимое для многоголовой машины Тьюринга, или возможна ли двухцветная универсальная машина Тьюринга с несколькими головками. Это также означает, что правила перезаписи являются полными по Тьюрингу, поскольку тройные правила эквивалентны правилам перезаписи. Расширяя ленту до двух измерений с головкой, выбирающей букву и ее 8 соседей, требуется только 2 цвета, например, цвет можно закодировать в вертикальном тройном шаблоне, таком как 110.
Кроме того, если расстояние между двумя головками является переменным (лента имеет «слабину» между головками), то она может имитировать любую систему почтовых бирок , некоторые из которых являются универсальными. [18]
Для тех, кто возьмется за разработку UTM точно так, как указал Тьюринг, см. статью Дэвиса в Copeland (2004). Дэвис исправляет ошибки в оригинале и показывает, как будет выглядеть пример запуска. Он успешно провел (несколько упрощенную) симуляцию.
Следующий пример взят из книги Тьюринга (1937). Подробнее об этом примере см. в разделе Примеры машин Тьюринга .
Тьюринг использовал семь символов {A, C, D, R, L, N, ; } для кодирования каждого 5-кортежа; как описано в статье Машина Тьюринга , его 5-кортежи имеют только типы N1, N2 и N3. Номер каждой « m -конфигурации» (инструкции, состояния) представлен «D», за которой следует унарная строка из A, например, «q3» = DAAA. Аналогичным образом он кодирует символы пробел как «D», символ «0» как «DC», символ «1» как DCC и т. д. Символы «R», «L» и «N» остаются такими, как есть.
После кодирования каждый 5-кортеж «собирается» в строку в порядке, показанном в следующей таблице:
Наконец, коды для всех четырех 5-кортежей объединяются в код, начинающийся с «;» и разделенный «;», т.е.:
Этот код он поместил на чередующиеся квадраты — «квадраты F» — оставив «квадраты E» (те, которые подлежат стиранию) пустыми. Окончательная сборка кода на ленте для U-машины состоит из размещения двух специальных символов («e») один за другим, затем кода, выделенного на чередующихся квадратах, и, наконец, символа двойного двоеточия « :: » (пробелы показаны здесь с «.» для ясности):
Таблица действий U-машины (таблица переходов состояний) отвечает за декодирование символов. Таблица действий Тьюринга отслеживает свое место с помощью маркеров "u", "v", "x", "y", "z", помещая их в "E-квадраты" справа от "отмеченного символа" - например, чтобы отметить текущую инструкцию z помещается справа от ";" x сохраняет место относительно текущей "m-конфигурации" DAA. Таблица действий U-машины будет перемещать эти символы (стирая их и помещая в разные места) по мере выполнения вычислений:
Таблица действий Тьюринга для его U-машины весьма запутана.
Роджер Пенроуз приводит примеры способов кодирования инструкций для универсальной машины с использованием только двоичных символов {0, 1} или {пусто, отметка |}. Пенроуз идет дальше и записывает весь свой код U-машины. Он утверждает, что это действительно код U-машины, огромное число, которое занимает почти 2 полных страницы единиц и нулей. [19]
Асперти и Риччиотти описали многоленточную UTM, определенную путем составления элементарных машин с очень простой семантикой, а не явным указанием ее полной таблицы действий. Этот подход был достаточно модульным, чтобы позволить им формально доказать правильность машины в помощнике доказательства Матиты . [20]
раздел 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9»
