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

Машина Тьюринга. Введение. Понятие машины тьюринга. Решение задачи [9:21]

Александр Шень — Машина Тьюринга // Постнаука [14:03]

001. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы - Н.К.Верещагин [1:23:33]

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

Ниже описана детерминированная машина Тьюринга. Есть её обобщения — см. вероятностная машина Тьюринга (а также недетерминированная машина Тьюринга).

Состав МТ

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

Виды команд:

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

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

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

Q={q₀, q₁, q₂, …, q_n} — множество состояний управляющего устройства с конечным состоянием (q₀);

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

A={a₁, a₂, …, a_k} — алфавит с пробелом (λ);

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

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

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

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

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

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

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

Виды командных строк:

s₁a₁s₂a₂M — при считывании символа a₁ в состоянии s₁ записать символ a₂, перейти в состояние s₂ и остаться на месте;

s₁a₁s₂a₂R — при считывании символа a₁ в состоянии s₁ записать символ a₂, перейти в состояние s₂ и осуществить сдвиг каретки вправо на 1 ячейку;

s₁a₁s₂a₂L — при считывании символа a₁ в состоянии s₁ записать символ a₂, перейти в состояние s₂ и осуществить сдвиг каретки влево на 1 ячейку.

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

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

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

Пример задачи

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

Программа для МТ

Таблица для программы

Примеры работы МТ:

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

1 — число 0;

11 — число 1;

111 — число 2;

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

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

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

Пример 1

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

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

Пример 2

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

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

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

Обобщения

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

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

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

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

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

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

Ссылки

• Участник:Logic-samara
• Машина Тьюринга в Абсурдопедии на Викии (юмористическая статья)