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

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2012)
Por favor, melhore este artigo inserindo fontes no corpo do texto quando necessário.

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

onde:

  • é o conjunto finito de estados
  • é o conjunto finito de símbolos/alfabeto de fita
  • é o símbolo vazio (o único símbolo que pode aparecer na fita infinitamente em qualquer passo da computação)
  • , é um subconjunto de não incluindo b. É o conjunto de símbolos de entrada
  • é a Função chamada função de transição, R é o movimento à direita.
  • é o estado inicial
  • é 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 (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"
Σ = , conjunto vazio
δ = ver tabela de estados abaixo
q0 = 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 | editar código-fonte]

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. ed. San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1