Máquinas de Turing somente de leitura e movimentos à direita – Wikipédia, a enciclopédia livre

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Julho de 2012)

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 | editar código-fonte]

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

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

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

Σ = ${\displaystyle \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:

Ver também[editar | editar código-fonte]

• AFD
• AFN
• Máquina de Turing somente de leitura
• Máquina de Turing

Referências[editar | editar código-fonte]

• 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  A referência emprega parâmetros obsoletos |coautor= (ajuda)