ВИДЫ МАШИН ТЬЮРИНГА

Аннотация. Что такое Машина Тьюринга, для чего она нужна? Пример Работы Машины Тьюринга. Существует 4 основных вида машин Тьюринга: недетерминированные, универсальные, вероятностные и квантовые машины Тьюринга.

Ключевые слова: машина Тьюринга, Детерминированная машина Тьюринга, Недетерминированная машина Тьюринга, Квантовая машина Тьюринга, Вероятностная машина Тьюринга.

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

1. Записывать элемент в ячейку, а еще стирание уже имеющегося элемента или же подмена иным элементом.
2. Сдвигать считывающую головку направо и налево.
3. Заменять внутреннее положение.

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

Вот пример созданной МТ. Данная машина заменяет введенной с клавиатуры последовательности букв «А» и «В» все имеющиеся значения ABA на AAB, при этом результат работы программы выводится в файл f,'Z: \12.txt'. Каждая замена выводится в новой строчке. Начало и конец последовательности обозначаются «*».

VARJ,I:INTEGER;

S:STRING;

F:TEXT;

LABELQ1,Q2,Q3,Q4,Q5,QZ;// Метки

BEGIN

assign(f,'Z: \12.txt');

rewrite(f);

    WRITELN('ВВЕДИТЕ ИСХОДНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ');

    WRITELN(F,'ВВЕДИТЕ ИСХОДНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ');

READLN(S);

WRITELN(F,S);//ABA-BAA

WRITELN(F);

    I:=2;

    Q1: IF S[I] = 'A' THEN BEGIN INC(I); GOTO Q2; END ELSE BEGIN GOTO Q5; END;

    Q2: IF S[I] = 'B' THEN BEGIN INC(I); GOTO Q3; END ELSE BEGIN DEC(I); GOTO Q5; END;

    Q3: IF S[I] = 'A' THEN BEGIN GOTO Q4; END ELSE BEGIN DEC(I); DEC(I); GOTO Q5; END;

    Q4: S[I]:='A'; DEC(I); S[I]:='A'; DEC(I); S[I]:='B'; I:=2; WRITELN(F,S); GOTO Q1;

    Q5: INC(I); IF S[I+2] = '*' THEN GOTO QZ ELSE GOTO Q1;

QZ: WRITELN (F,'РЕЗУЛЬТАТ РАБОТЫ МТ');

WRITELN;

WRITELN(F,S);

CLOSE(F);

END.

Результат тестирования:

ВВЕДИТЕ ИСХОДНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ

*ABABABA*

*BAABABA*

*BABAABA*

*BBAAABA*

*BBAABAA*

*BBABAAA*

*BBBAAAA*

РЕЗУЛЬТАТ РАБОТЫ МТ

*BBBAAAA*

Принято выделять 4 ведущих облика машин Тьюринга:

1. Недетерминированная МТ
2. Универсальная МТ
3. Вероятностная МТ
4. Квантовая МТ

Детерминированная (обычная, классическая) МТ содержит функцию перехода, которая по композиции текущего состояния и знака на ленте определяет 3 вещества: знак, который станет записан на ленте, назначение смещения головки по ленте и свежее положение конечного автомата. К примеру, F на ленте в состоянии 5 несомненно определяет переход в положение 6, запись на ленту знака G и движение головки на 1 сделку налево. В случае недетерминированной машины Тьюринга, композиция текущего состояния автомата и знака на ленте имеет возможность допускать некоторое количество переходов. К примеру, F на ленте и положение 5 допускает как положение 6 с записью на ленту знака G и смещением головки направо, например и положение 7 с записью на ленту знака H и смещением головки налево.

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

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

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

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

Есть еще другое определение:

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

Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой наименее 1/3, именуется классом BPP.

Квантовая МТ — отвлеченная МТ, применяемая для моделирования квантового компьютера. Дает собой несложную модель, которая, в то же время, имеет возможность обрисовать всевозможные квантовые вычисления. Всякий квантовый метод имеет возможность быть формально описан как кое-какая квантовая МТ. В первый раз похожие модели были предложены в 1985 году в работе Дэвида Дойча (Оксфордский университет)

В реальное время Квантовая МТ применяются довольно редко.

Список литературы:

1. Викиучебник: ru.wikibooks.org/wiki/Машина_Тьюринга
2. Википедия: ru.wikipedia.org/wiki/Недетерминированная_машина_Тьюринга
3. А. В. Овсянников, Ю.А. Пикман АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ. Часть I: docplayer.ru/amp/40006617-A-v-ovsyannikov-yu-a-pik...-dannyh-chast-i.html
4. Студенческие файлы МГУ: StudFiles.net/preview/7507133/page:23/