Máquinas de Turing somente de leitura e movimentos à direita

Maquinas de Turing somente de leitura e movimentos à direita são um tipo particular de Máquina de Turing que reconhecem apenas linguagens regulares por se comportarem como Autômatos finitos deterministicos.

Definição editar

A definição é baseada em uma máquina de fita única infinita definida para ser uma 7-upla

$M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ onde:

$Q$ é o conjunto finito de estados
$\Gamma$ é o conjunto finito de símbolos/alfabeto de fita
$b\in \Gamma$ é o símbolo vazio (o único símbolo que pode aparecer na fita infinitamente em qualquer passo da computação)
$\Sigma$ , é um subconjunto de $\Gamma$ não incluindo b. É o conjunto de símbolos de entrada
$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{R\}$ é a Função chamada função de transição, R é o movimento à direita.
$q_{0}\in Q$ é o estado inicial
$F\subseteq Q$ é o conjunto de estados finais ou estados de aceitação

No caso dessas Máquinas de Turing o único movimento é para a direita. Deve existir ao menos um elemento no conjunto $F$ (um estado HALT) para a máquina aceitar uma linguagem regular (não incluindo a linguagem vazia).

Um exemplo de Maquinas de Turing somente de leitura e movimentos à direita é:

Q = { A, B, C, HALT }

Γ = { 0, 1 }

b = 0 = "vazio"

Σ =

\varphi

, conjunto vazio

δ = ver tabela de estados abaixo

q₀ = A = estado inicial

F = o elemento de um conjunto de estados finais {HALT}

Tabela de estados para uma máquina somente de leitura de 3 estados e dois símbolos:

	Estado atual A:			Estado atual B:			Estado atual C:
	Símbolo escrito:	Movimento na fita:	Próximo estado:	Símbolo escrito:	Movimento na fita:	Próximo estado:	Símbolo escrito:	Movimento na fita:	Próximo estado:
símbolo lido é 0:	1	R	B	1	R	A	1	R	B
símbolo lido é 1:	1	R	C	1	R	B	1	N	HALT

Ver também editar

Referências editar

Davis, Martin; Ron Sigal, Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science 2nd ed. San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1