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
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 AFD AFN Máquina de Turing somente de leitura Máquina de Turing
Referências
Categoria:Máquina de Turing