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

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

ماشین‌های تورینگ
ماشین
ماشین محاسبه تورینگ ماشین تورینگ متناوب ماشین تورینگ کوانتومی ماشین تورینگ غیرقطعی ماشین خواندنی تورینگ ماشین راستگرد خواندنی تورینگ ماشین تورینگ احتمالی ماشین تورینگ چندمسیره ماشین‌های هم‌ارز با ماشین تورینگ مثال‌های ماشین تورینگ
علم
آلن تورینگ رده:ماشین تورینگ

تعریف

برای تعریف باید از ۷فاکتور نامحدود استفاده میکنیم. ${\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\subseteq Q}$ وضیعت نهایی یا حالت پذیرفته شده است.

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

{Q = { A، B، C، HALT

b = 0 = blank

Σ = ${\displaystyle \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. Unknown parameter |coauthors= ignored (|author= suggested) (help)