Машина Тьюринга

Материал из Циклопедии
Перейти к: навигация, поиск
Машина Тьюринга. Введение. Понятие машины тьюринга. Решение задачи [9:21]
Александр Шень — Машина Тьюринга // Постнаука [14:03]
001. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы - Н.К.Верещагин [1:23:33]

Машина Тьюринга (МТ) — это абстрактная вычислительная машина для выполнения программ, предложенная английским математиком Аланом Мэтисоном Тьюрингом в 1936 году. Ниже описана детерминированная машина Тьюринга. Есть ее обобщения — см. вероятностная машина Тьюринга (а также недетерминированная машина Тьюринга).

Содержание

[править] Состав МТ

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

[править] Виды команд:

  • сдвиг вправо
  • сдвиг влево
  • остаться на месте
  • запись символа алфавита в ячейку
  • перейти в состояние из множества

Введём обозначения:

n — число состояний управляющего устройства без конечного;

Q={q0, q1, q2, …, qn} — множество состояний управляющего устройства с конечным состоянием (q0);

k — число символов алфавита;

A={a1, a2, …, ak} — алфавит с пробелом (λ);

s1 — номер состояния, в котором управляющее устройство находится до выполнения команды;

s2 — номер состояния, в которое управляющее устройство переходит после выполнения команды;

a1 — считываемый символ a1;

a2 — записываемый символ a2;

R — сдвиг вправо;

L — сдвиг влево;

M — оставание на месте.

[править] Виды командных строк:

s1a1s2a2M — при считывании символа a1 в состоянии s1 записать символ a2, перейти в состояние s2 и остаться на месте;

s1a1s2a2R — при считывании символа a1 в состоянии s1 записать символ a2, перейти в состояние s2 и осуществить сдвиг каретки вправо на 1 ячейку;

s1a1s2a2L — при считывании символа a1 в состоянии s1 записать символ a2, перейти в состояние s2 и осуществить сдвиг каретки влево на 1 ячейку.

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

После запуска программы на МТ возможны следующие варианты:

  • работа может закончиться если система переходит в терминальное (конечное) состояние;
  • работа никогда не закончится (т.е.программа составлена не корректно).

[править] Пример задачи

МТ11.JPG, где x, y - неотрицательные целые числа.

[править] Программа для МТ

МТ12.JPG

[править] Таблица для программы

МТ13.JPG

[править] Примеры работы МТ:

Введём обозначения:

1 — число 0;

11 — число 1;

111 — число 2;

1x+1 — неотрицательное целое число x;

1y+1 — неотрицательное целое число y;

1x+1λ1y+1 — набор значений аргументов (x,y).

[править] Пример 1

Входные данные: 111λ1.

МТ14.JPG

Выходные данные: λ0λλλλ1.

[править] Пример 2

Входные данные: 11λ111.

МТ15.JPG

Выходные данные: λ1011.

  • Заметим, что машина Поста во многом аналогична машине Тьюринга.

[править] Обобщения

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

Недетерминированная машина Тьюринга выдаст ответ 1, если существует хотя бы один путь развития вычисления, на котором выдается ответ 1, и 0 — в противном случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).

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

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

[править] Другие алгоритмы

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты