В информатике универсальная машина Тьюринга ( UTM ) — это машина Тьюринга , способная вычислить любую вычислимую последовательность, [1] как описано Аланом Тьюрингом в его основополагающей статье «О вычислимых числах с применением к проблеме Entscheidungs». Здравый смысл мог бы сказать, что универсальная машина невозможна, но Тьюринг доказывает, что это возможно. [а] Он предположил, что мы можем сравнить человека в процессе вычисления действительного числа с машиной, которая способна выполнять только конечное число условий q 1 : q 2 . .... qI; которые будут называться «м-конфигурациями». [2] Затем он описал работу такой машины, как описано ниже, и заявил:
Я утверждаю, что эти операции включают в себя все те операции, которые используются при вычислении числа. [3]
Алан Тьюринг представил идею такой машины в 1936–1937 годах. Этот принцип считается источником идеи компьютера с хранимой программой , использованного Джоном фон Нейманом в 1946 году для «электронного вычислительного прибора», который теперь носит имя фон Неймана: архитектура фон Неймана . [4]
Дэвис приводит убедительный аргумент в пользу того, что концепция Тьюринга о том, что сейчас известно как «компьютер с хранимой программой», о размещении «таблицы действий» — инструкций для машины — в той же «памяти», что и входные данные, сильно повлияла на Джона. Концепция фон Неймана о первом американском компьютере с дискретными символами (а не аналоговом) — EDVAC . Дэвис цитирует журнал Time по этому поводу, что «каждый, кто стучит по клавиатуре… работает над воплощением машины Тьюринга», и что «Джон фон Нейман [построен] на основе работ Алана Тьюринга». [5]
Дэвис утверждает, что компьютер Тьюринга « Автоматическая вычислительная машина » (ACE) «предвосхитил» понятия микропрограммирования ( микрокода ) и RISC- процессоров. [6] Кнут цитирует работу Тьюринга над компьютером ACE как разработку «аппаратного обеспечения для облегчения связи подпрограмм»; [7] Дэвис также называет эту работу использованием Тьюрингом аппаратного «стека». [8]
Поскольку машина Тьюринга способствовала созданию компьютеров , UTM поощрял развитие молодых компьютерных наук . Ранний, если не самый первый, ассемблер был предложен «молодым талантливым программистом» для EDVAC. [9] «Первая серьезная программа фон Неймана… [была] просто эффективной сортировкой данных». [10] Кнут отмечает, что возврат из подпрограммы, встроенный в саму программу, а не в специальные регистры, принадлежит фон Нейману и Гольдстайну. [b] Кроме того, Кнут утверждает, что
Можно сказать, что первой интерпретационной процедурой была «универсальная машина Тьюринга»... Интерпретационные процедуры в общепринятом смысле были упомянуты Джоном Мочли в его лекциях в Школе Мура в 1946 году… Тьюринг также принимал участие в этом развитии; Под его руководством были написаны системы интерпретации для компьютера Pilot ACE. [11]
Дэвис кратко упоминает операционные системы и компиляторы как результаты концепции программы как данных. [12]
Благодаря такому кодированию таблиц действий в виде строк машины Тьюринга в принципе становятся возможными отвечать на вопросы о поведении других машин Тьюринга. Однако большинство этих вопросов неразрешимы , а это означает, что рассматриваемую функцию невозможно вычислить механически. Например, в оригинальной статье Тьюринга было показано, что проблема определения того, остановится ли произвольная машина Тьюринга на определенном входе или на всех входах, известная как проблема остановки , в целом неразрешима. Теорема Райса показывает, что любой нетривиальный вопрос о производительности машины Тьюринга неразрешим.
Универсальная машина Тьюринга может вычислить любую рекурсивную функцию , определить любой рекурсивный язык и принять любой рекурсивно перечислимый язык . Согласно тезису Чёрча-Тьюринга , проблемы, решаемые универсальной машиной Тьюринга, — это именно те проблемы, которые можно решить с помощью алгоритма или эффективного метода вычислений , при любом разумном определении этих терминов. По этим причинам универсальная машина Тьюринга служит стандартом для сравнения вычислительных систем, а система, которая может имитировать универсальную машину Тьюринга, называется полной по Тьюрингу .
Абстрактной версией универсальной машины Тьюринга является универсальная функция , вычислимая функция, которую можно использовать для вычисления любой другой вычислимой функции. Теорема UTM доказывает существование такой функции.
Без ограничения общности можно предположить, что входные данные машины Тьюринга имеют алфавит {0, 1}; любой другой конечный алфавит может быть закодирован с помощью {0, 1}. Поведение машины Тьюринга M определяется ее функцией перехода. Эту функцию также можно легко закодировать как строку в алфавите {0, 1}. Размер алфавита M , количество лент в нем и размер пространства состояний можно вывести из таблицы функции перехода. Выделенные состояния и символы могут быть идентифицированы по их положению, например, первые два состояния могут по соглашению быть состояниями начала и остановки. Следовательно, каждую машину Тьюринга можно закодировать как строку в алфавите {0, 1}. Кроме того, мы утверждаем, что каждая недопустимая кодировка сопоставляется с тривиальной машиной Тьюринга, которая немедленно останавливается, и что каждая машина Тьюринга может иметь бесконечное количество кодировок, дополняя кодировку произвольным количеством (скажем) единиц в конце, как и комментарии. работать на языке программирования. Неудивительно, что мы можем добиться такого кодирования, учитывая существование числа Гёделя и вычислительную эквивалентность между машинами Тьюринга и µ-рекурсивными функциями . Аналогично, наша конструкция сопоставляет каждой двоичной строке α машину Тьюринга M α .
Начав с приведенной выше кодировки, в 1966 году Ф. К. Хенни и Р. Э. Стернс показали, что если имеется машина Тьюринга M α , которая останавливается на входе x за N шагов, то существует многоленточная универсальная машина Тьюринга, которая останавливается на входах α , x (заданных на разные ленты) в CN log N , где C — машинная константа, которая не зависит от длины входного сигнала x , но зависит от размера алфавита M , количества лент и количества состояний. По сути, это симуляция, использующая обозначение Big O Дональда Кнута . [13] Соответствующий результат для пространственной сложности, а не временной сложности, заключается в том, что мы можем моделировать таким образом, чтобы использовать максимум ячеек CN на любом этапе вычислений, то есть симуляцию. [14]
Когда Алан Тьюринг придумал идею универсальной машины, он имел в виду простейшую вычислительную модель, достаточно мощную для расчета всех возможных функций, которые можно вычислить. Клод Шеннон впервые явно поставил вопрос о поиске минимально возможной универсальной машины Тьюринга в 1956 году. Он показал, что двух символов достаточно, пока используется достаточное количество состояний (или наоборот), и что всегда можно обменять состояния на символы. Он также показал, что не может существовать никакой универсальной машины Тьюринга с одним состоянием.
Марвин Мински открыл универсальную машину Тьюринга с 7 состояниями и 4 символами в 1962 году, используя системы с 2 тегами . Другие небольшие универсальные машины Тьюринга с тех пор были найдены Юрием Рогожиным и другими, расширив этот подход моделирования системы тегов. Если обозначить через ( m , n ) класс UTM с m состояниями и n символами, то будут найдены следующие кортежи: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) и (2, 18). [15] [16] [17] Машина Рогожина (4, 6) использует только 22 инструкции, и неизвестен стандартный UTM меньшей сложности описания.
Однако обобщение стандартной модели машины Тьюринга допускает еще меньшие UTM. Одним из таких обобщений является разрешение бесконечно повторяющегося слова на одной или обеих сторонах входных данных машины Тьюринга, что расширяет определение универсальности и известно как «полуслабая» или «слабая» универсальность соответственно. Небольшие слабо универсальные машины Тьюринга, имитирующие клеточный автомат по Правилу 110, были даны для пар состояние-символ (6, 2), (3, 3) и (2, 4). [18] Доказательство универсальности трехсимвольной машины Тьюринга с двумя состояниями Вольфрама еще больше расширяет понятие слабой универсальности, допуская определенные непериодические начальные конфигурации. Другие варианты стандартной модели машины Тьюринга, которые дают небольшие 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 , некоторые из которых являются универсальными. [19]
Для тех, кто возьмется за разработку 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» остаются как есть.
После кодирования каждый пятикортеж «собирается» в строку в порядке, показанном в следующей таблице:
Наконец, коды для всех четырех кортежей из пяти частей объединяются в код, начинающийся с ";" и разделены знаком ";" то есть:
Этот код он поместил на чередующиеся квадраты — «F-квадраты», оставив «E-квадраты» (те, которые подлежат стиранию) пустыми. Окончательная сборка кода на ленте для U-машины состоит из размещения двух специальных символов («e») один за другим, затем кода, разделенного на чередующиеся квадраты, и, наконец, символа с двойным двоеточием « :: » (пробелы здесь отмечены знаком «.» для ясности):
Таблица действий U-машины (таблица переходов состояний) отвечает за декодирование символов. Таблица действий Тьюринга отслеживает свое место с помощью маркеров «u», «v», «x», «y», «z», помещая их в «Е-квадраты» справа от «отмеченного символа» - например , чтобы отметить текущую инструкцию, z ставится справа от ";" x сохраняет свое место по отношению к текущей DAA «m-конфигурации». Таблица действий U-машины будет перемещать эти символы (стирать их и размещать в разных местах) по мере выполнения вычислений:
Таблица действий Тьюринга для его U-машины очень сложна.
Роджер Пенроуз приводит примеры способов кодирования инструкций для универсальной машины, используя только двоичные символы { 0, 1 } или { пробел, отметка | }. Пенроуз идет дальше и записывает весь код своей U-машины. Он утверждает, что это действительно U-машинный код, огромное число, занимающее почти две полные страницы, состоящие из единиц и нулей. [20]
Асперти и Риччиотти описали многоленточный UTM, определяемый путем составления элементарных машин с очень простой семантикой, а не путем явного указания полной таблицы действий. Этот подход был достаточно модульным, чтобы позволить им формально доказать корректность машины в помощнике по доказательству Matita . [ нужна цитата ]
Оригинал статьи и исправления
Другие цитируемые работы
раздел 1.4 «Машины как струны и универсальная машина Тьюринга» и 1.7 «Доказательство теоремы 1.9»
