Машина Тьюринга как распознающее устройство

F Определение: Машиной Тьюринга называется пятерка следующих объектов: Т =(К, Н, d, q ₀, F) (формальное определение машины Тьюринга),

где: К – конечное множество состояний машины;

Н – конечное множество символов рабочей ленты;

К Ç Н =Æ, L, R Ï Н;

q ₀ – начальное состояние, q ₀Î К;

F – подмножество заключительных состояний, F Ì K;

d – функция, отображающая множества К´Н в семейство всех подмножеств множества К ´ (Н È{ L, R }).

Информацию, хранимую в памяти машины Тьюринга, и положение управляющей головки удобно представлять в виде так называемой конфигурации машины, которая задается цепочкой символов следующего вида: a_{i 1} a_{i 2}... a_{ik -1} q a_ik... a_in, где a_{i l} – символы рабочей ленты, q – состояние машины.

Пусть a и b – две конфигурации машины Тьюринга.

Запись a |¾ b используется тогда, когда машина может перейти из конфигурации a в конфигурацию b за один рабочий такт.

Если машина переходит из конфигурации a в конфигурацию b за несколько рабочих тактов, то используется запись a |¾^* b.

F Определение: Машина Тьюринга вычисляет функцию

f (a), если q ₀ a |¾^* b,

где a Î H *,

l(a) ³1,

b – конфигурация, в которую входит одно из заключи­тельных состояний машины.

Цепочку, полученную из b вычеркиванием символа состояния и всех вхождений пустых символов, будем считать значением функции f от аргумента a.

Все машины Тьюринга делятся на детерминированные и недетерминированные.

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

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

F Определение: Линейно-ограниченный автомат – это машина Тьюринга, рабочая лента которой ограничена длиной рассматри­ваемой цепочки. Линейно-ограниченным автоматом называется пятерка следующих объектов: В =(К, Н, d, q ₀, F),

где К – непустое множество состояний;

Н – непустое множество символов рабочей ленты,
КÇН= Æ;

d - функция, отображающая множество К ´ Н в семейство всех подмножеств множества К ´ Н ´{ L, R, N };

q ₀ – начальное состояние, q ₀Î К;

F – подмножество заключительных состояний, F Í K \ { q ₀}.

Утверждение: Класс языков, допускаемых линейно-ограниченными автоматами совпадает с классом НС языков.

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

F Определение: Машиной Тьюринга с входной лентой называется шестерка следующих объектов:

T ’=(K, Н, S, d, q ₀, F),

где К – конечное множество состояний машины;

Н – конечное множество символов рабочей ленты;

S – конечное множество символов входной ленты.

d: К ´ Н ´SÞ К ´ (Н È{ L, R }).

q ₀ – начальное состояние;

F – подмножество заключительных состояний.

Существует еще одна разновидность машин Тьюринга – машина с входной и выходной лентами. Выходная лента служит для записи синтаксической структуры. Определение такой машины подобно определению машины Т ’ с той разницей, что на каждом такте работы машина с выходной лентой может на нее записать некоторую цепочку символов. Поэтому вводится в рассмотрение еще одно конечное множество символов D – множество символов выходной ленты, а функция d имеет следующий вид d: К ´ Н ´SÞ К ´ (Н È{ L, R })´D*.