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

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

تعریف

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

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

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

{Q = { A، B، C، HALT

b = 0 = blank الگو:سخ

Σ = $\phi$, 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

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

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

منابع

• الگو:Cite book