ماشین راستگرد خواندنی تورینگ

ماشین راستگردخواندنی توریگ (به انگلیسی: Read-only right moving Turing machines) نوعی خاص از ماشین تورینگ است.

تعریف

برای تعریف باید از ۷فاکتور نامحدود استفاده میکنیم. $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ که در آن:

• $Q$ حالتی محدودی از وضیعت هاست.
• $\Gamma$ مجموعه متناهی از سمبل ها و نمادهاست.
• $b\in \Gamma$ نماد صفر(تنها نمادی که امکان اتفاق افتادنش به طور نامحدود حتی طی محاسبات هست. )
• $\Sigma$ یک زیر مجموعه از $\Gamma$ که شامل نماد های ورودی جز b هست.
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{R\}$ تابعی به نام تابع انتقال هست ،و R راستگرد است.
• $q_{0}\in Q$ حالت اولیه است.
• $F\subseteq Q$ وضیعت نهایی یا حالت پذیرفته شده است.

مثالی از ماشین راستگرد خواندنی تورینگ

{Q = { A، B، C، HALT

b = 0 = blank

Σ = $\varphi$, empty set
δ = see state-table below
F = the one element set of final states HALT
جدول وضیعت برای ماشین فقط خواندنی با 3 حالت و 2 نماد

	Current state A:			Current state B:			Current state C:
	Write symbol:	Move tape:	Next state:	Write symbol:	Move tape:	Next state:	Write symbol:	Move tape:	Next state:
tape symbol is 0:	1	R	B	1	R	A	1	R	B
tape symbol is 1:	1	R	C	1	R	B	1	N	HALT

جستارهای وابسته

• ماشین‌های تعین‌پذیر حالات متناهی
• اتوماتون تعین‌ناپذیر متناهی
• ماشین‌های حالات متناهی
• ماشین تورینگ

منابع

• Davis, Martin (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed. ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1. {{cite book}}: |edition= has extra text (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)