Что такое состояние машины тьюринга. Тренажер для изучения универсального исполнителя. Машины Тьюринга: обсуждение

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

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

Устройство

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

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

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

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

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q i a j →q i1 a j1 d k (если головка находится в состоянии q i , а в обозреваемой ячейке записана буква a j , то головка переходит в состояние q i1 , в ячейку вместо a j записывается a j1 , головка делает движение d k , которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример

Пример машины Тьюринга для умножения чисел в унарной системе счисления . Запись правила «q i a j →q i1 a j1 R/L/N» следует понимать так: q i - состояние при котором выполняется это правило, a j - данные в ячейке, в которой находится головка, q i1 - состояние в которое нужно перейти, a j1 - что нужно записать в ячейку, R/L/N - команда на перемещение.

Машина работает по следующему набору правил:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1→q 0 1R	q 1 1→q 2 aR	q 2 1→q 2 1L	q 3 1 → q 4 aR	q 4 1→q 4 1R			q 7 1→q 2 aR
×	q 0 ×→q 1 ×R		q 2 ×→q 3 ×L		q 4 ×→q 4 ×R		q 6 ×→q 7 ×R		q 8 ×→q 9 ×N
=			q 2 =→q 2 =L		q 4 =→q 4 =R			q 7 =→q 8 =L
a			q 2 a→q 2 aL	q 3 a→q 3 aL	q 4 a→q 4 aR		q 6 a→q 6 1R	q 7 a→q 7 aR	q 8 a→q 8 1L
*	q 0 →q 0 R			q 3 →q 6 R	q 4 *→q 5 1R
						q 5 →q 2 *L

Описание состояний:

Начало
q 0	начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1
q 1	заменяем «1» на «а» и переходим в состояние q2
Переносим все «1» из первого числа в результат
q 2	ищем «х» слева. При нахождении переходим в состояние q3
q 3	ищем «1» слева, заменяем её на «а» и переходим в состояние q4. В случае если «1» закончились, находим «*» и переходим в состояние q6
q 4	переходим в конец (ищем «» справа), заменяем «» на «1» и переходим в состояние q5
q 5	добавляем «*» в конец и переходим в состояние q2
Обрабатываем каждый разряд второго числа
q 6	ищем «х» справа и переходим в состояние q7. Пока ищем заменяем «а» на «1»
q 7	ищем «1» или «=» справа при нахождении «1» заменяем его на «а» и переходим в состояние q2 при нахождении «=» переходим в состояние q8
Конец
q 8	ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем заменяем «а» на «1»
q 9	терминальное состояние (остановка алгоритма)

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

Начало. Находимся в состоянии q 0 , ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.

1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q 0 и над символом «*». Это правило из 1-го столбца 5-й строки - q 0 *→q 0 *R. Это значит, что мы переходим в состояние q 0 (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111x11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q 0 1 (1-й столбец 1-я строка) обрабатывается правилом q 0 1→q 0 1R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.

Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц - значит умножение завершено.

Полнота по Тьюрингу

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

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

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

Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины D {\displaystyle D} и входные данные X {\displaystyle X} , которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные X {\displaystyle X} .

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

На машине Тьюринга можно имитировать машину Поста , нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера - оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. - может быть очень большой, но, тем не менее, всегда конечна. Теоретический предел количества информации, которая может находиться внутри заданной поверхности, с точностью до множителя 1 / ln ⁡ 2 {\displaystyle 1/\ln {2}} равен энтропии чёрной дыры с той же площадью поверхности.

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

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

Маши́на Тью́ринга (МТ) - абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма .

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

Устройство машины Тьюринга

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

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

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q i a j →q i1 a j1 d k (если головка находится в состоянии q i , а в обозреваемой ячейке записана буква a j , то головка переходит в состояние q i1 , в ячейку вместо a j записывается a j1 , головка делает движение d k , которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления . Машина работает по следующему набору правил:

Набор правил	Набор правил


q 0 ×→q 1 ×R



	q 6 ×→q 7 ×R
q 2 ×→q 3 ×L
q 3 1 → q 4 aR


q 4 ×→q 4 ×R

Умножим с помощью МТ 3 на 2 в единичной системе:

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

Полнота по Тьюрингу

Основная статья : Полнота по Тьюрингу

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

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

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

Варианты машины Тьюринга

Машина Тьюринга, работающая на полубесконечной ленте

В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.

Таким образом Машина Тьюринга формально описывается набором двух алфавитов:

A={a1, a2, a3, …, an} — внешний алфавит, служит для записи исходных данных

Q={q1, q2, q3,…, qm} — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = {a0,a1,…,an} (В нашем случае A={0, 1})

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

1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

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

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = {q0,q1,…,qm}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте)
· новое состояние автомата

В приведенной выше таблице алфавит A ={0, 1, _} (содержит 3 символа), а внутренний алфавит Q={q1, q2, q3, q4, q0}, q0 — состояние, заставляющее каретку остановиться.

Рассмотрим несколько задач решением. Скачать машину Тьюринга Вы можете на сайте в разделе СКАЧАТЬ .

Задача 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».

q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — возвращается назад на 1 ячейку «желает что-то другое», т. е. переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)

q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.

Посмотреть работу программы можно на видео:

Задача 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:

Из 001101011101 получим 000000000000 1111111.

Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.

Приступим к рассуждениям. Определим, какие состояния необходимы каретке и сколько.

q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)

q2) ничего не менять, двигаться к концу последовательности

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

q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5

q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1

Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.

Получим такую программу:

Работу Машины Тьюринга можете посмотреть на видео ниже.

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

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента , разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита : алфавит входных символов A = {a 0 , a 1 , ..., a m }и алфавит состояний Q = {q 0 , q 1 , ..., q p }. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q .) Состояние q 0 называется пассивным . Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q 1 называется начальным . Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит пустая буква а 0 - признак того, что ячейка пуста).

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

Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую буквуai он видит, а также в зависимости от своего состояния qj автомат может выполнять следующие действия:

· записать новую букву в обозреваемую ячейку;
· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
· перейти в новое состояние.

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

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

Клетка (q j , a i ) определяется двумя параметрами - символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние q m (которое может в частном случае совпадать с прежним состоянием q j ). Следующую команду нужно искать в m -й строке таблицы на пересечении со столбцом a l (букву a l автомат видит после сдвига).

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

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

Машина Поста

Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

1) V j - поставить метку, перейти к j-й строке программы.

2) X j - стереть метку, перейти к j-й строке программы.

3) <- j - сдвинуться влево, перейти к j-й строке программы.

a. j - сдвинуться вправо, перейти к j-й строке программы.

4) ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

5) ! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

Работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);