Машина Тьюринга
Машина Тьюринга (МТ) — абстрактная вычислительная машина для выполнения программ, предложенная английским математиком Аланом Мэтисоном Тьюрингом в 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 ячейку.
Для работы машины Тьюринга нужно задать программу и её начальное состояние (т. е. состояние управляющей системы, состояние ленты и позицию каретки). Предполагается, что неопределённая часть ленты заполнена символами пробела, т.е. она чистая.
После запуска программы на МТ возможны следующие варианты:
- работа может закончиться если система переходит в терминальное (конечное) состояние;
- работа никогда не закончится (т.е.программа составлена не корректно).
Пример задачи[править]
, где x, y - неотрицательные целые числа.
Программа для МТ[править]
Таблица для программы[править]
Примеры работы МТ:[править]
Введём обозначения:
1 — число 0;
11 — число 1;
111 — число 2;
1x+1 — неотрицательное целое число x;
1y+1 — неотрицательное целое число y;
1x+1λ1y+1 — набор значений аргументов (x,y).
Пример 1[править]
Входные данные: 111λ1.
Выходные данные: λ0λλλλ1.
Пример 2[править]
Входные данные: 11λ111.
Выходные данные: λ1011.
- Заметим, что машина Поста во многом аналогична машине Тьюринга.
Обобщения[править]
Недетерминированная машина Тьюринга — обобщение детерминированной машины Тьюринга, в которой при каждом переходе можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок). Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
Недетерминированная машина Тьюринга выдаст ответ 1, если существует хотя бы один путь развития вычисления, на котором выдается ответ 1, и 0 — в противном случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).
Вероятностная машина Тьюринга — обобщение детерминированной машины Тьюринга, в которой из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода, машина выбирает один из вариантов с некоторой вероятностью.
Другие алгоритмы[править]
- метод математической индукции;
- алгоритмы в арифметике;
- алгоритмы перевода чисел;
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест;
- логистические алгоритмы;
- алгоритмы решения транспортных задач;
- численные методы;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- синтез автомата Мили;
- синтез автомата Мура.
Ссылки[править]
- Участник:Logic-samara
- Машина Тьюринга в Абсурдопедии на Викии (юмористическая статья)