МАШИНА ТЬЮРИНГА


Определение. МАШИНОЙ ТЬЮРИНГА называется формальная система (устройство), задаваемое четверкой объектов , где
— конечный алфавит ленты,
— конечное множество состояний устройства управления,
— начальная конфигурация машины Тьюринга, где — строка в алфавите ленты.
— программа машины Тьюринга. Множество есть отображение множества декартового произведения множества состояний устройства управления на множество алфавита ленты в множество декартового произведения множеств состояния устройства управления, алфавита ленты и множества перемещения ленты , то есть , где .

ТЕОРЕМА 2.1. О машинах Тьюринга и грамматиках.
Машина Тьюринга представляет грамматику типа 0.

ДОКАЗАТЕЛЬСТВО.
A. Построим грамматику , которая производит те же действия, что и машина Тьюринга. Для этого отождествим терминальный алфавит грамматики и алфавит ленты машины Тьюринга, множество нетерминальных знаков грамматики и множество состояний устройства управления машины Тьюринга . В качестве аксиомы грамматики зададим состояние и добавим это состояние в множество . .
B. Множество продукций грамматики строим следующим образом:
1. Для всех команд машины Тьюринга вида в множество продукций добавляем продукции вида .
2. Для всех команд машины Тьюринга вида в множество продукций добавляем продукции вида .
3. Для всех команд машины Тьюринга вида в множество продукций добавляем продукции вида , для всех .
C. В множество продукций добавляем продукцию вида , порождающая исходные данные машины Тьюринга.
D. Построенная таким образом грамматика порождает ( распознает) те же строки, что и машина Тьюринга, при переходе из состояния с некоторым состоянием ленты в состояние .
Действительно, если применяется команда машины Тьюринга типа 1 , то может быть применена продукция грамматики типа; если применяется команда типа 2, то может быть применена продукция типа 2; при применении команды типа 3 существует одна из продукций, приводящая к тем же действиям, что и команда машины Тьюринга.
В Общем случае обратное не верно, но существует эквивалентное преобразование грамматики типа 0 в форму, представимую машиной Тьюринга.
Окончание доказательства.

Машина Тьюринга вычисляет функцию , заданную на множестве строк , где — универсальное множество, образованное лентой машины Тьюринга, если:
1. Для каждой строки существует строка такая, что машина Тьюринга будучи запушена из начального состояния и строкой на ленте, останавливается, когда на ленте записана строка . .
2. Для всех строк машина Тьюринга не останавливается, то есть не переходит в состояние .

Определение. ЭКВИВАЛЕНТНЫМИ такие машины Тьюринга, которые вычисляют одну и ту же функцию .