Správně se pohybující Turingovy stroje jen pro čtení - Read-only right moving Turing machines - Wikipedia

Správně se pohybující Turingovy stroje jen pro čtení jsou konkrétním typem Turingův stroj.

Definice

Definice založená na jediném nekonečném pásku definovaném jako 7-n-tice

${ displaystyle M = langle Q, Gamma, b, Sigma, delta, q_ {0}, F rangle}$ kde

${ displaystyle Q}$ je konečná sada státy
${ displaystyle Gamma}$ je konečná množina pásková abeceda / symboly
${ displaystyle b in Gamma}$ je prázdný symbol (jediný symbol, který se může na pásku vyskytovat nekonečně často v kterémkoli kroku během výpočtu)
${ displaystyle Sigma}$ , podmnožina ${ displaystyle Gamma}$ nezahrnující b je množina vstupní symboly
${ displaystyle delta: Q krát gama pravá šipka Q krát gama krát {R }}$ je funkce volal přechodová funkce, R je pravý pohyb (pravý posun).
${ displaystyle q_ {0} v Q}$ je počáteční stav
${ displaystyle F subseteq Q}$ je sada finále nebo přijímající státy

V případě těchto typů Turingových strojů je jediným pohybem doprava. Musí existovat alespoň jeden prvek sady $F$ (A STŮJ stavu), aby stroj přijal běžný jazyk (bez prázdného jazyka).

Příklad Turingova stroje se správným pohybem jen pro čtení

{ displaystyle Q = {A, B, C, { text {HALT}} }}

{ displaystyle Gamma = {0,1 }}

{ displaystyle b = 0}

„prázdné“

{ displaystyle Sigma = varnothing}

, prázdná sada

{ displaystyle delta =}

viz tabulka stavů níže

{ displaystyle q_ {0} = A}

, počáteční stav

{ displaystyle F =}

sada jednoho prvku konečných stavů:

{ displaystyle {{ text {HALT}} }}

Tabulka stavů pro 3 stavy, 2 symboly pouze pro čtení

symbol pásky	Napište symbol	Přesuňte pásku	Další stav	Napište symbol	Přesuňte pásku	Další stav	Napište symbol	Přesuňte pásku	Další stav
	Aktuální stav A			Aktuální stav B			Aktuální stav C
0	1	R	B	1	R	A	1	R	B
1	1	R	C	1	R	B	1	N	STŮJ

Viz také

Reference

Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Druhé vydání: Vyčíslitelnost, složitost a jazyky a logika: Základy teoretické informatiky (2. vyd.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.