Máquinas de Turing somente de leitura e movimentos à direita
Saltar para a navegação
Saltar para a pesquisa
Predefinição:Sem notas Predefinição:Turing 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 |