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

Материал из ALL
Перейти к: навигация, поиск

Машина Тьюринга (МТ) — это абстрактная вычислительная машина для выполнения программ, предложенная английским математиком Аланом Мэтисоном Тьюрингом в 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.

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

Другие алгоритмы:

Другие разделы

Ссылки