Машина Тьюринга — гипотетическое вычислительное устройство, впервые придуманное Аланом Тьюрингом в 1936 году. Машины Тьюринга манипулируют символами на потенциально бесконечной полосе ленты в соответствии с конечной таблицей правил и обеспечивают теоретическую основу для понятия компьютерного алгоритма.
Хотя ни одна из следующих моделей не продемонстрировала большей мощности, чем модель одноленточной, односторонней, бесконечной, многосимвольной машины Тьюринга, их авторы определили и использовали их для исследования вопросов и решения проблем с большей легкостью, чем если бы они придерживались модели a -машины Тьюринга.
эквивалентность Тьюринга
Можно показать, что многие машины, которые, как можно было бы подумать, обладают большей вычислительной мощностью, чем простая универсальная машина Тьюринга, не обладают большей мощностью. [1] Они могут вычислять быстрее, возможно, или использовать меньше памяти, или их набор инструкций может быть меньше, но они не могут вычислять более мощно (т. е. больше математических функций). ( Тезис Чёрча-Тьюринга предполагает, что это верно: что все, что может быть «вычислено», может быть вычислено некоторой машиной Тьюринга.)
Модели последовательных машин
Все нижеперечисленное называется «последовательными моделями машин», чтобы отличать их от «параллельных моделей машин». [2]
Модель машины Тьюринга
Машина Тьюринга (как он ее называл) имела левосторонний конец и правосторонний бесконечный конец. Он предоставил символы əə для обозначения левого конца. Было разрешено конечное число символов ленты. Инструкции (если это была универсальная машина), а также «вход» и «выход» были написаны только на «F-квадратах», а маркеры должны были появляться на «E-квадратах». По сути, он разделил свою машину на две ленты, которые всегда двигались вместе. Инструкции появлялись в табличной форме, называемой «5-кортежами», и не выполнялись последовательно.
Следующие модели представляют собой одноленточные машины Тьюринга, но с ограничениями (i) ограниченными символами ленты {метка, пробел}, и/или (ii) последовательными, компьютерными инструкциями, и/или (iii) полностью атомизированными действиями машины.
Эмиль Пост в независимом описании вычислительного процесса сократил разрешенные символы до эквивалентного двоичного набора отметок на ленте { "mark", "blank"=not_mark }. Он изменил понятие "ленты" с односторонней бесконечности вправо на бесконечный набор комнат, в каждой из которых по листу бумаги в обоих направлениях. Он разбил тьюринговские 5-кортежи на 4-кортежи — инструкции движения, отделенные от инструкций печати/стирания. Хотя его модель 1936 года неоднозначна в этом отношении, модель Поста 1947 года не требовала последовательного выполнения инструкций.
Его чрезвычайно простая модель может эмулировать любую машину Тьюринга, и хотя его Формулировка 1 1936 года не использует слова «программа» или «машина», она фактически является формулировкой очень примитивного программируемого компьютера и связанного с ним языка программирования , в котором блоки действуют как неограниченная память битовых цепочек, а набор инструкций составляет программу.
В влиятельной статье Хао Ван сократил « формулировку 1 » Поста до машин, которые все еще используют двустороннюю бесконечную двоичную ленту, но чьи инструкции проще — будучи «атомарными» компонентами инструкций Поста — и по умолчанию выполняются последовательно (как «компьютерная программа»). Его заявленная главная цель состояла в том, чтобы предложить в качестве альтернативы теории Тьюринга ту, которая «более экономична в основных операциях». Его результатами стали «программные формулировки» множества таких машин, включая 5-инструкционную W-машину Вана с набором инструкций
и его наиболее существенно сокращенная 4-командная B-машина Ванга («B» означает «базовый») с набором команд
в котором даже нет инструкции ERASE-SQUARE.
Многие авторы позднее представили варианты машин, обсуждаемых Ваном:
Минский развил идею Вана с помощью своей версии модели (многоленточной) «счетной машины», которая допускала движение SHIFT-LEFT и SHIFT-RIGHT отдельных головок, но не печатала вообще. [3] В этом случае ленты заканчивались бы слева, каждый конец был бы отмечен одной «меткой», указывающей конец. Он смог сократить это до одной ленты, но за счет введения движения многоленточного квадрата, эквивалентного умножению и делению, а не гораздо более простого { SHIFT-LEFT = УМЕНЬШЕНИЕ, SHIFT-RIGHT = УВЕЛИЧЕНИЕ }.
Дэвис, добавив явную инструкцию HALT к одной из машин, обсуждаемых Ваном, использовал модель с набором инструкций
а также рассматривались варианты с ленточными алфавитами размером больше 2.
В соответствии с проектом Вана по поиску теории, эквивалентной Тьюрингу, «экономичной в основных операциях» и желая избежать безусловных переходов, заметным теоретическим языком является язык «P» с четырьмя инструкциями, введенный Коррадо Бёмом в 1964 году — первый язык императивного « структурного программирования » «без GOTO», для которого было доказано, что он является полным по Тьюрингу .
В практическом анализе часто используются различные типы многоленточных машин Тьюринга. Многоленточные машины похожи на одноленточные, но имеется некоторое постоянное число k независимых лент.
Если таблица действий имеет не более одной записи для каждой комбинации символа и состояния, то машина является «детерминированной машиной Тьюринга» (DTM). Если таблица действий содержит несколько записей для комбинации символа и состояния, то машина является «недетерминированной машиной Тьюринга» (NDTM). Эти две машины вычислительно эквивалентны, то есть можно превратить любую NDTM в DTM (и наоборот ) , хотя они обычно имеют разное время выполнения. Это можно доказать с помощью построения.
Забывчивая машина Тьюринга — это машина Тьюринга, в которой для каждой длины ввода движение различных головок является фиксированной функцией времени, независимой от ввода. Другими словами, существует предопределенная последовательность, в которой различные ленты сканируются, продвигаются и записываются. Фактические значения, которые записываются на ленту на любом шаге, могут по-прежнему отличаться для каждого ввода этой длины. Пиппенджер и Фишер показали, что любое вычисление, которое может быть выполнено многоленточной машиной Тьюринга за n шагов, может быть выполнено забывчивой двухленточной машиной Тьюринга за шагов. [4]
Забывчивые машины соответствуют пошаговым линейным образом комбинационным логическим схемам, когда сложность таблицы переходов принимается постоянной. Таким образом, можно реализовать вычисления как задачи схем по размеру и глубине (см. Сложность схемы ). Это улучшает исходный результат Кука и Левина .
Петер ван Эмде Боас объединяет все машины этого типа в один класс, «регистровые машины». [2] Однако исторически сложилось так, что в литературе наиболее примитивный член этой группы, то есть «счетная машина», также именуется «регистровой машиной». А наиболее примитивное воплощение «счетной машины» иногда называют «машиной Мински».
Примитивная модель регистровой машины по сути является многоленточной 2-символьной пост-Тьюринговой машиной, поведение которой ограничено, так что ее ленты действуют как простые «счетчики».
Ко времени Мелзака, Ламбека и Мински понятие «компьютерной программы» породило другой тип простой машины с множеством лент с левым концом, вырезанных из ленты Пост-Тьюринга. Во всех случаях модели допускают только два символа ленты {mark, blank}. [3]
Некоторые версии представляют положительные целые числа только как строки/стопку знаков, разрешенных в «регистре» (т. е. ленте с левым концом), и пустую ленту, представленную счетчиком «0». Минский исключил инструкцию PRINT за счет предоставления своей модели обязательной одиночной метки в левом конце каждой ленты. [3]
В этой модели односторонние ленты-регистры рассматриваются как «счетчики», их инструкции ограничены только двумя (или тремя, если инструкция TEST/DECREMENT атомизирована). Два общих набора инструкций следующие:
Хотя его модель сложнее, чем это простое описание, модель «камней» Мелзака расширила это понятие «счетчика», чтобы разрешить сложение и вычитание нескольких камешков.
Мелзак признал пару серьезных дефектов в своей модели регистра/счетчика-машины: [5] (i) Без формы косвенной адресации он не смог бы «легко» показать, что модель эквивалентна Тьюрингу , (ii) Программа и регистры находились в разных «пространствах», поэтому самомодифицирующиеся программы были бы нелегкими. Когда Мелзак добавил косвенную адресацию к своей модели, он создал модель машины с произвольным доступом.
(Однако, используя гёделевскую нумерацию инструкций, Минский предложил доказательство того, что при такой нумерации общерекурсивные функции действительно возможны; он предлагает доказательство того, что μ-рекурсия действительно возможна [3] ).
В отличие от модели RASP, модель RAM не позволяет действиям машины изменять ее инструкции. Иногда модель работает только в режиме регистр-регистр без аккумулятора, но большинство моделей, похоже, включают аккумулятор.
Ван Эмде Боас делит различные модели оперативной памяти на ряд подтипов: [2]
RASP — это RAM, в котором инструкции хранятся вместе с данными в одном «пространстве» — т. е. последовательности регистров. Понятие RASP было описано, по крайней мере, еще Кифенгстом. Его модель имела «мельницу» — аккумулятор, но теперь инструкции находились в регистрах вместе с данными — так называемая архитектура фон Неймана . Когда RASP имеет чередующиеся четные и нечетные регистры — четные содержат «код операции» (инструкцию), а нечетные содержат ее «операнд» (параметр), то косвенная адресация достигается простой модификацией операнда инструкции. [6]
Первоначальная модель RASP Элгота и Робинсона имела только три инструкции в стиле модели регистровой машины [7] , но они поместили их в регистровое пространство вместе с их данными. (Здесь COPY занимает место CLEAR, когда один регистр, например, «z» или «0», начинается с 0 и всегда содержит его. Этот трюк не является чем-то необычным. Единица 1 в регистре «unit» или «1» также полезна.)
Модели RASP допускают как косвенную, так и прямую адресацию; некоторые допускают также «непосредственные» инструкции, например «Загрузить аккумулятор константой 3». Инструкции могут быть из строго ограниченного набора, например, следующие 16 инструкций Хартманиса. [8] Эта модель использует аккумулятор A. Мнемоника та же, что использовали авторы (их CLA — «загрузить аккумулятор» константой или из регистра; STO — «сохранить аккумулятор»). Их синтаксис следующий, за исключением переходов: «n, <n>, <<n>>» для «непосредственного», «прямого» и «косвенного»). Переходы осуществляются через две «инструкции передачи» TRA — безусловный переход путем прямого «n» или косвенного «< n >» заталкивания содержимого регистра n в счетчик инструкций, TRZ (условный переход, если аккумулятор равен нулю, таким же образом, как и TRA):
Относительно поздно появилась Машина Модификации Хранения Шёнхаге или указательная машина . Другая версия — машина Колмогорова-Успенского и предложение Кнута о «связывающем автомате». (Для ссылок см. указательная машина ). Как и диаграмма конечного автомата, узел испускает по крайней мере два помеченных «ребра» (стрелки), которые указывают на другой узел или узлы, которые в свою очередь указывают на другие узлы и т. д. Внешний мир указывает на центральный узел.
Любая из вышеперечисленных ленточных машин может быть оснащена входными и выходными лентами; любая из вышеперечисленных регистровых машин может быть оснащена выделенными входными и выходными регистрами. Например, модель указателя-машины Шёнхаге имеет две инструкции, называемые " вход λ 0 , λ 1 " и " выход β ".
Трудно изучать сублинейную пространственную сложность на многоленточных машинах с традиционной моделью, потому что входной размер n уже занимает место n . Таким образом, для изучения небольших классов DSPACE мы должны использовать другую модель. В некотором смысле, если мы никогда не «пишем» на входную ленту, мы не хотим брать с себя плату за это пространство. И если мы никогда не «читаем» с нашей выходной ленты, мы не хотим брать с себя плату за это пространство.
Мы решаем эту проблему, вводя k -струнную машину Тьюринга с входом и выходом. Это то же самое, что и обычная k -струнная машина Тьюринга, за исключением того, что функция перехода δ ограничена, так что входная лента никогда не может быть изменена, и так что выходная головка никогда не может двигаться влево. Эта модель позволяет нам определять детерминированные классы пространств, меньшие, чем линейные. Машины Тьюринга с входом и выходом также имеют ту же временную сложность, что и другие машины Тьюринга; по словам Пападимитриу 1994 Prop 2.2:
Машины Тьюринга с k -строками и входом, и выходом могут быть использованы в формальном определении ресурса сложности DSPACE . [9]
