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

ماشین راستگردخواندنی توریگ نوعی خاص از ماشین تورینگ است.

تعریف

برای تعریف باید از ۷فاکتور نامحدود استفاده میکنیم. $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; Ron Sigal, Elaine J. Weyuker (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.