Машина Тьюринга как вычислительная модель

§ 1. Детерминированная машина Тьюринга.

§ 2. Языки, допускаемые машиной Тьюринга.

§ 3. Многоленточная машина Тьюринга.

§ 4. Недетерминированная машина Тьюринга.

§ 5. Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.

Самостоятельные занятия

Примеры вычислений на детерминированной одноленточной машине Тьюринга. 3], раздел 2, глава1.

[1], глава 8.

В логике с помощью понятия машины Тьюринга строится теория неразрешимых проблем, однако в вычислительной практике чаще приходится иметь дело с разрешимыми, но «трудно решаемыми» проблемами. Выбирая и здесь в качестве вычислительной модели машину Тьюринга, мы руководствуемся тем, что она проста и допускает те же языки, что и компьютер, причем сложность вычислений на машине Тьюринга полиномиальна от числа шагов компьютера.

Машина Тьюринга представляет собой абстрактную вычислительную машину, состоящую из управления с конечным числом состояний и бесконечной ленты, разделенной на ячейки, в каждой из которых хранится один ленточный символ, и одна из ячеек является текущей позицией ленточной головки. Формальная запись машины Тьюринга — это упорядоченный набор

M = (X, Q, q ₀, F, I), где.

X — внешний алфавит символов (букв на ленте), включающий символ ;

Q — конечный алфавит внутренних состояний;

q₀ — инициальное состояние (начало работы), q₀ Q;

Fмножество заключительных состояний, F Q;

I — множество инструкций, или машинных команд, каждая из которых принадлежит множеству.

(Q F) X {} Q X {R, L, S}.

Переходы осуществляются на основе текущего состояния и обозреваемого считывающей головкой символа к следующему состоянию, переписыванию символа и сдвигу головки (вправо R, влево L, на месте S).

Можно определить функцию переходов.

: (Q F) X* Q X* {R, L, S}, где X* -слова в алфавите X.

В случае однозначной функции машина Тьюринга называется детерминированной машиной Тьюринга.

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

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

В качестве примера рассмотрим работу детерминированной машины Тьюринга, вычисляющей функцию m — n. Упорядоченную пару натуральных чисел (m, n) представляем как слово 0^m10ⁿ в алфавите X {} = {0,1}, ячейки слева и справа от которого содержат символ .

q₀0 Rq₁ Состояния Символ.

q₁0 0Rq₁ 0 1.

q₁1 1Rq₂ q₀ Rq₁ 1Sq₅ 0Sq₅

q₂0 1Lq₃ q₁ 0Rq₁ 1Rq₂

q₂1 1Rq₂ q₂ 1Lq₃ 1Rq₂ Lq₄

q₃1 1Lq₃ q₃ 0Lq₃ 1Lq₃ Rq₀

q₃0 0Lq₃ q₄ 0Lq₄ Lq₄ 0Sq₅

q₃ Rq₀ q₅ Rq₅

q₂ Lq₄ *.

q₄1 Lq₄

Таблица 1. Программа вычисления функции m — n,.

q₄0 0Lq₄ где функция переходов задается таблицей.

q₄ 0Sq₅

q₀1 1Sq₅ *.

q₅1 Rq₅

Машина Тьюринга M допускает (отвергает) слово X^*, если она останавливается на нем, придя в допускающее (заключительное) состояние. Машина допускает язык L X^*, если она допускает все слова языка L. Машина M распознает язык L X^*, если она допускает все слова из L и останавливается на словах из X^* L, не находясь в заключитель ном состоянии. Языки, допускаемые машиной Тьюринга, назовем рекурсивно перечислимым.

Язык L допускается (распознается) за полиномиальное время, если существует машина M, которая допускает (распознает) язык L, причем всякое слово L допускается (распознается) за время O (n^k), где n — длина слова, а k — не зависящее от число.

Теперь можно определить класс P, как множество языков L {0,1}^*, распознаваемых за полиномиальное время.

Теорема. Класс P есть множество языков, допускаемых за полиномиальное время.

Доказательство. В одну сторону тривиально, если машина M распознает язык L, то она и допускает язык L. Обратно, пусть язык L допускается машиной M за время O (n^k), т. е. существует константа c, что любое слово из L длины n допускается не более, чем за T = cn^k шагов. С другой стороны, слова, не принадлежащие L, не допускаются ни за какое время. Построим машину M, которая на слове моделирует не более Т = cn^k шагов машины M и останавливается, выдавая 1, если M ()=1, в противном случае — останавливается, сделав Т = cn^k шагов, выдавая на выход 0. Таким образом, машина M распознает язык L и сложностной класс P можно рассматривать, как множество языков, допускаемых за полиномиальное время.

Многоленточная машина Тьюринга

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

За один переход осуществляются следующие действия:

управление переходит в новое состояние,.

на каждой ленте записывается новый (или тот же) символ;

считывающие головки каждой из лент независимо сдвигаются на одну ячейку (R, L, S).

Языки, допускаемые одноленточными машинами Тьюринга, рекурсивно перечислимы. Допустимы ли многоленточными машинами не рекурсивно перечислимые языки? Ответ в следующей теореме.

Теорема. Каждый язык L, допускаемый многоленточной машиной Тьюринга, рекурсивно перечислим.

Доказательство. Одноленточную машину Тьюринга можно представить, как многодорожечную, задавая ее аргументы в виде кортежей. При этом одна дорожка хранит данные, а другая отметку. Смоделируем k — ленточную машину M как многодорожечную машину N, содержащую 2k дорожек, где каждая вторая содержит маркер, указывающий позицию головки соответствующей ленты. Машина N должна посетить каждый из маркеров головок k лент и изменить соответствующим образом символ, представляющий соответствующую ленту, перемещая маркер в том направлении, как это происходило на соответствующей ленте. Наконец, N изменяет состояние М, записанное в конечном управлении N. В качестве допускающих состояний N выбираются все те состояния, в которых запоминалось допускающее состояние M. Таким образом, машина M и N одновременно допускают язык L. Но все языки, допускаемые одноленточной машиной N, рекурсивно перечислимы, поэтому рекурсивно перечислимы все языки, допускаемые многоленточной машиной M.

Теорема. Время, необходимое одноленточной машине N для имитации n переходов k-ленточной машины M, есть O (n²).

Доказательство. После n переходов машины M маркеры головок разделены не более, чем 2n клетками, так что и машине N надо сдвинуться не более, чем на 2n клеток вправо, чтобы найти все маркеры головок. Теперь ей надо совершить проход влево, изменяя содержимое M лент и сдвигая головочные маркеры, что потребует не более 2n сдвигов влево плюс не более 2k переходов для изменения направления движения и записи маркера в клетку. Таким образом, число переходов N для имитации одного из переходов машины M не более 4n+2k, т. е. O (n). Для n переходов требуется времени в n раз больше, т. е. O (n²).

Различие во времени вычисления на машинах с разным числом лент сохраняет полиномиальную сложность и для одноленточной машины ограничено сT (n)², а емкость — сS (n) (для входа длины n), где T (n), S (n) — параметры k-ленточных машин. Зависимость между емкостью и временем для k-ленточных машин линейная: S kT; для входа длины n T k^s+n.

Недетерминированные машины Тьюринга

По причинам, которые вскоре будут понятны, недетерминированные машины Тьюринга являются ключевым понятием в теории NP-полных задач. Недетерминированная машина Тьюринга отличается от обычной (детерминированной) машины Тьюринга тем, что может иметь более одного перехода от текущей конфигурации к следующей. Недетерминированная машина допускает слово , если существует хотя бы одна цепочка конфигураций, ведущая от начальной конфигурации в заключительную. Существование других последовательностей конфигураций, не ведущих в заключительное (допускающее) состояние не имеет значение. Работу недетерминированной машины на входе можно представить в виде дерева, где каждый путь из корня в лист представляет некоторую последовательность возможных шагов машины. Если кратчайшая последовательность возможных шагов работы машины, которая оканчивается допускающей конфигурацией, то есть время, затраченное машиной на обработку входа. Если на входе никакая последовательность не приводит к допускающей конфигурации, то время, затраченное на обработку не определено. Считается, что недетерминированная машина Тьюринга на входе параллельно выполняет все возможные последовательности шагов, пока не достигнет допускающего состояния или окажется, что ее программа не применима к полученной конфигурации.

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

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

Обозначим через L (M) множество всех слов X*, допускаемых машиной M, L (M) называют языком машины M.

Теорема. Если M недетерминированная машина с полиномиальной временной сложностью T (n), то существует детерминированная машина M ', с L (M ') = L (M) и временной сложностью O (c^{T (n)}).

Доказательство. Доказательство основывается на том, что для любой недетерминированной машины Тьюринга M строится детерминированная машина M ', которая исследует последовательности конфигураций (пути в дереве недетерминированной машины) и если находит хотя бы одну с допускаемым состоянием, то сама переходит в допускаемое состояние. Обследованные конфигурации помещаются в очередь, длины k (k=1,2…) Построим детерминированную многоленточную машину M ', моделирующую недетерминированную машину M. Первая лента машины M ' хранит последовательность конфигураций машины M и метку на текущее состояние последней. Записи слева от метки предполагаются исследованными и их в дальнейшем игнорируют. Конфигурации справа рассматриваются в порядке очереди. Программа машины M хранится в конечном управлении M '. Обработка текущей конфигурации на первой ленте состоит в следующем:

• — Машина M ' проверяет состояние и обозреваемый символ и, если состояние допускающее, также переходит в допускающее состояние.
• — Если состояние не допускающее и из данной конфигурации есть k переходов, то M ' использует вторую ленту для создания k копий, которые записываются в конце очереди на ленте 1.
• — M ' изменяет k конфигураций в соответствии с программой машины M.
• — M ' перемещает отметку текущей конфигурации на следующую справа и цикл повторяется с шага 1.

Допустим, что m есть максимальное число выборов машины M в любой конфигурации. Тогда существует одно начальное состояние M, не более m конфигураций, достижимых за 1 шаг, не более m² конфигураций, достижимых за 2 шага и т. д. Таким образом, после n переходов машина M может достичь не более 1+ m +m² +…+mⁿ nmⁿ конфигураций. Порядок, в котором машина M ' исследует конфигурации, называется «поиском в ширину», т. е. M ' исследует все достижимые конфигурации машины M за 0 шагов, достижимые за 1 шаг и т. д.

Допускающая конфигурация машины M будет рассмотрена машиной M ' в числе первых nmⁿ конфигураций. Таким образом, если машина M допускает, то машина M ' также допускает, т. е. L (M) = L (M ').

Отметим, что работа построенной детерминированной машины M' может потребовать экспоненциально большего времени, чем время работы недетерминированной машины M, которую она моделирует. Разница между полиномиальным и экспоненциальным временем — это граница того, что можно решить с помощью компьютера, а что практически нерешаемо.

Теорема. Если M недетерминированная машина Тьюринга с емкостной сложностью S (n), то найдется детерминированная машина Тьюринга M' с емкостной сложностью O (S²(n)) и L (M') = L (M).

Доказательство. Пусть M недетерминированная машина Тьюринга (возможно k-ленточная) с емкостной сложностью S (n). Тогда число различных конфигураций, в которые машина M может попасть из начальной с входом длины n, не превосходит некоторого числа c^{S (n)}, точнее Q (X+1)^{k S (n)} (S (n))^k, где k — число лент. Тогда число переходов от конфигурации C₁ к конфигурации C₂ (С₁+ С₂) на любой из лент не превосходит c^{S (n)}. Можно выяснить, существует ли переход С₁+ С₂ за 2i шагов, проверив для всех C₃ существует ли переход С₁+ С₃ и С ₃+ С₂ за i шагов. После каждого обращения к процедуре число i уменьшается вдвое.

Идея моделирования машиной M' работы машины M приведена в доказательстве предыдущей теоремы. Стратегия работы машины M' - установить приведет ли начальная конфигурация C₀ к какой-нибудь допускающей конфигурации C_f. Чтобы найти верхнюю емкостную границу для машины M', расположим конфигурации (длины O (S (n))) на стеках того же размера. В каждый момент времени число фрагментов стека не превосходит 1+ log c^{S (n)}, т. е. O (S (n)). Для всего стека машины M потребуется O (S² (n)) ячеек.

Теорема. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга M = (X, Q, q₀, F, I) с временной сложностью T (n), то он допускается одноленточной недетерминированной машиной с временной сложностью O (T²(n)).

Доказательство. Пусть M₁ одноленточная недетерминированная машина Тьюринга, имеющая на ленте 2k дорожек, т. е. ленточные символы машины M₁ представляются 2k-членными кортежами, в которых на нечетных местах стоят символы алфавита X, а на четных — либо символ, либо маркер #. Дорожки с нечетными номерами соответствуют k лентам машины M, а каждая дорожка с четным номером 2j содержит символ во всех ячейках, кроме одной, где стоит маркер #, отмечающий положение головки машины M на ленте j, которой соответствует дорожка 2j-1. Машина M₁ моделирует один шаг работы машины M следующим образом. Допустим, что вначале головка машины M₁ обозревает клетку, содержащую самую левую головку машины M.

Головка машины M₁ движется вправо, пока не минует все k маркеров положений головок на дорожках с четными номерами. При этом M₁ запоминает в своем состоянии символы, обозреваемые каждой из головок машины M. Теперь M₁ делает недетерминированное развлетвление, исходя из состояния машины M, которое машина M₁ запомнила в своем состоянии, и обозреваемых машиной M на лентах символов, которые машина M₁ также нашла.

Выбрав для моделирования шаг машины M, машина M₁ изменяет в соответствии с ним состояние машины M, которое она помнит в своем состоянии. Затем M₁ сдвигает свою головку влево и проходит все маркеры, изменяя ленточный символ на дорожке над маркером и сдвигая маркер не более чем на одну клетку (L, R, S).

Машина M₁ промоделировала один шаг работы машины M. Действия машины M₁ на этом шаге детерминированы. Ее головка находится правее левого маркера не более чем на две ячейки. Начиная с этого маркера цикл можно повторить.

Если машина M допускает цепочку длины n, то совершает при этом не более T (n) переходов. Очевидно, что в последовательности из T (n) шагов головки мащины M могут разойтись не более чем на T (n) клеток, и, значит, M₁ может смоделировать один шаг этой последовательности не более чем за O (T (n)) своих шагов. Таким образом, M₁ допускает цепочку, выполняя не более чем O (T² (n)) переходов.

Следствие 1. Если язык допускается k-ленточной детерминированной машиной Тьюринга с временной сложностью T (n), то он допускается одноленточной детерминированной машиной Тьюринга с временной сложностью O (T²(n)).

Следствие 2. Если язык L допускается k-ленточной недетерминированной машиной Тьюринга с емкостной сложностью S (n), то он допускается одноленточной недетерминированной машиной Тьюринга с емкостной сложностью S (n).

Следствие 3. Если язык допускается k-ленточной детерминированной машиной Тьюринга с емкостной сложностью S (n), то он допускается одноленточной детерминированной машиной Тьюринга с емкостной сложностью S (n).

Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга

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

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

Процессор состоит из устройства управления (УУ) и арифметического устройство (АУ). Устройство управления содержит счетчик тактов, команд и т. д., вырабатывает управляющие сигналы для выполнения команд, передачи данных и т. д. Процессор содержит регистры операндов, линии связи и линии задержки для непосредственной реализации процессов вычислений.

Наряду с процессором и памятью компьютеру необходимы еще устройства ввода/вывода.

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

Для имитации компьютера на машине Тьюринга существенны две вещи:

существуют ли инструкции, выполняемые компьютером, и недоступные для машины Тьюринга;

работает ли компьютер быстрее машины Тьюринга, т. е. более, чем полиномиальная зависимость разделяет время работы компьютера и машины Тьюринга при решении какой-то проблемы.

Неформальная модель реального компьютера:

• — память, состоящая из последовательности слов и их адресов. В качестве адресов будут использоваться натуральные числа 0,1, …;
• — программа компьютера, записанная в слова памяти, каждое из которых представляет простую инструкцию. Допускается «непрямая адресация» по указателям;
• — каждая инструкция использует конечное число слов и изменяет значение не более одного слова;
• — имеются слова памяти с быстрым доступом (регистры), но скорость доступа к различным словам влияет лишь на константный сомножитель, что не искажает полиномиальную зависимость.

Возможная конструкция машины Тьюринга для имитации компьютера представлена на рис.

Рис.

Машина имеет несколько лент. Первая лента представляет всю память компьютера — адреса и значения (в двоичной системе). Адреса заканчиваются маркером *, значения — маркером #. Начало и конец записей 1-й ленты обозначаются маркером $. Вторая лента — «счетчик инструкций», содержит одно двоичное целое, представляющее одну из позиций считываюшей головки на первой ленте, адрес инструкции, которая должна быть выполнена следующей. Третья лента содержит адрес и значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции машина Тьюринга должна найти значение по одному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и перемещается на нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера. Четвертая лента имитирует входной файл. Пятая лента — рабочая память, служит для выполнения вычислений. Допускающая инструкция машины Тьюринга соответствует выводу на печать в выходном файле.

Функционирование такой имитирующей машины:

• 1. Найдя на 1-й ленте адрес, совпадающий с номером инструкции на 2-й ленте, исследуем значение по нему и копируем на 3-ю ленту. Первые биты инструкции задают действие (копировать, вставить, ветвиться и т. д.), оставщиеся биты — адрес или адреса, используемые в этом действии.
• 2. Если в инструкции содержится значение по некоторому адресу, то этот адрес копируется на 3-ю ленту, а позиция инструкции на 2-ю дорожку 1-й ленты.
• 3. Далее инструкция выполняется. С новым значением можно сделать следующее:

скопировать по другому адресу;

Второй адрес извлекается из инструкции, помещается на 3-ю ленту, находится на 1-й ленте и значение по нему копируется в зарезервированное для него пространство. Если для нового значения надо больше (меньше) памяти, чем для старого, пространство изменяется путем сдвига, а именно, на рабочую ленту копируется часть ленты справа от того места, куда надо поместить новое значение;

новое значение записывается на 1-ю ленту;

рабочая часть копируется обратно на 1-ю ленту справа от нового значения.

прибавить найденное значение по другому адресу;

Ищем второй адрес на первой ленте, выполняем сложение значения по этому адресу и записанному на 3-й ленте.

перейти к выполнению инструкции по адресу, записанному на 3-й ленте, для чего лента 3 копируется на ленту 2, и цикл инструкций начинается снова.

4. Выполнив инструкцию (не являющуюся переходом), прибавляем 1 к счетчику на ленте 2 и вновь начинаем цикл инструкции.

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

Время работы машины Тьюринга, имитирующей компьютер

Введем следующие ограничения на модель компьютера:

— Ни одна компьютерная инструкция не должна порождать слово, длиннее, чем на 1 бит, своих операндов.

Инструкция, применяемая к словам длины m должна выполняться не более, чем за 0(m²) шагов на многоленточной машине Тьюринга.

Назовем такие операции допустимыми.

Этим условиям удовлетворяют сложение, сдвиг на 1 бит, сравнение значений, которые выполняются на многоленточной машине Тьюринга за 0(m) шагов. А также умножение m-битовых целых, если его имитировать с помощью m последовательных сложений со сдвигами на 1 бит влево. Время выполнения операции умножения будет пропорционально квадрату длины сомножителей.

Теорема. Для компьютера, обладающего указанными свойствами, описанная выше модель машины Тьюринга может имитировать m шагов компьютера не более, чем за 0(m³) шагов.

Доказательство. Вначале первая лента содержит только программу компьютера, длина которой не зависит от n (числа шагов выполнения инструкций). Наибольшее из компьютерных слов или адресов, встречающихся в программе, обозначим через c, а через d — число слов программы.

После выполнения n шагов компьютер не может породить слово, длиннее c+n, и не может создать или использовать адрес, занимающий больше c+n битов. Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому после выполнения n инструкций имеем d+n адресов. Каждый адрес-значение занимает не более 2(c+n) +2 разрядов, а после выполнения n инструкций не больше 2(d+n)(c+n+1), или 0(n²).

Для просмотра адресов одной инструкции компьютера требуется времени 0(n²), слова имеют длину 0(n), а инструкции выполняются машиной Тьюринга за время 0(n²), сдвиг для создания пространства для нового слова включает копирование данных объемом 0(n²) с ленты 1 на рабочую ленту и обратно. Таким образом, машина Тьюринга имитирует один шаг компьютера за 0(n²) своих шагов, а n шагов можно проимитировать за 0(n³) шагов машины Тьюринга.

Теорема. Выполнение n шагов работы компьютера можно проимитировать на одноленточной машине Тьюринга не более чем за 0(n⁶) шагов.

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