Право движущиеся машины Тьюринга только для чтения

Доступные только для чтения машины Тьюринга, движущиеся вправо, - это особый тип машины Тьюринга .

Определение [ править ]

Определение, основанное на единственной бесконечной ленте, заданной как кортеж из семи

${\ Displaystyle M = \ langle Q, \ Gamma, b, \ Sigma, \ delta, q_ {0}, F \ rangle}$ где

• ${\ displaystyle Q}$конечный набор состояний
• ${\ displaystyle \ Gamma}$конечный набор ленточного алфавита / символов
• ${\ displaystyle b \ in \ Gamma}$- пустой символ (единственный символ, который может встречаться на ленте бесконечно часто на любом этапе вычислений)
• ${\ displaystyle \ Sigma}$, подмножество не включая b - это набор входных символов${\ displaystyle \ Gamma}$
• ${\ displaystyle \ delta: Q \ times \ Gamma \ rightarrow Q \ times \ Gamma \ times \ {R \}}$- функция, называемая функцией перехода , R - движение вправо (сдвиг вправо).
• ${\ displaystyle q_ {0} \ in Q}$это начальное состояние
• ${\ Displaystyle F \ substeq Q}$это набор конечных или принимающих состояний

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

Пример машины Тьюринга, движущейся вправо, только для чтения [ править ]

${\ displaystyle Q = \ {A, B, C, {\ text {HALT}} \}}$

${\ Displaystyle \ Gamma = \ {0,1 \}}$

${\ displaystyle b = 0}$, "пустой"

${\displaystyle \Sigma =\varnothing }$, пустой набор

${\displaystyle \delta =}$ см. таблицу состояний ниже

${\displaystyle q_{0}=A}$, начальное состояние

${\displaystyle F=}$ одноэлементный набор конечных состояний:${\displaystyle \{{\text{HALT}}\}}$

Таблица состояний для машины с 3 состояниями, 2 символа только для чтения [ править ]

См. Также [ править ]

• DFA
• NFA
• Конечный автомат
• Машина Тьюринга только для чтения
• Машина Тьюринга
• Примеры машины Тьюринга

Ссылки [ править ]

• Дэвис, Мартин; Рон Сигал; Элейн Дж. Вейкер (1994). Второе издание: вычислимость, сложность, языки и логика: основы теоретической информатики (2-е изд.). Сан-Диего: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.