Право движущиеся машины Тьюринга только для чтения - Википедия - Read-only right moving Turing machines

Машины Тьюринга
Машина
Эквиваленты машины Тьюринга Примеры машины Тьюринга Галерея машин Тьюринга
Варианты
Переменная машина Тьюринга Дифференцируемый нейронный компьютер Недетерминированная машина Тьюринга Квантовая машина Тьюринга Машина Пост-Тьюринга Вероятностная машина Тьюринга Машина Тьюринга только для чтения Право движущиеся машины Тьюринга только для чтения Многолента машина Тьюринга Многодорожечная машина Тьюринга Симметричная машина Тьюринга Общая машина Тьюринга Однозначная машина Тьюринга Универсальная машина Тьюринга Зенон машина
Наука
Алан Тьюринг Категория: машина Тьюринга

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

Определение

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

${ Displaystyle M = langle Q, Gamma, b, Sigma, delta, q_ {0}, F rangle}$ куда

• ${ displaystyle Q}$ конечный набор состояния
• ${ displaystyle Gamma}$ конечный набор лента алфавит / символы
• ${ displaystyle b in Gamma}$ это пустой символ (единственный символ, который может встречаться на ленте бесконечно часто на любом этапе вычислений)
• ${ displaystyle Sigma}$, подмножество ${ displaystyle Gamma}$ не включая b - это набор входные символы
• ${ 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 символа только для чтения

	Текущее состояние А			Текущее состояние B			Текущее состояние C
символ ленты	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние
0	1	р	B	1	р	А	1	р	B
1	1	р	C	1	р	B	1	N	HALT

Смотрите также

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

Рекомендации

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