Revisão de Teoria da Computação: Decidibilidade, Propriedades de Linguagens e Complexidade
Revisão Final de Teoria da Computação
1) Problemas de Decidibilidade e Reconhecimento
1a) Linguagem L: Máquina de Turing (MT) e Movimentos
L = {<M,w> | M move para a direita exatamente 2 vezes quando roda sobre w}
M só pode ler os 2 primeiros caracteres da entrada.
O número de configurações distintas de M é maxconf = |alfabeto da fita|5 · |K|. Se M entrar de novo na mesma configuração, ele fará a mesma coisa que fez na primeira vez.
Algoritmo de Decisão:
Rode M em w por maxconf + 1 passos ou até parar ou mover para a direita 3 vezes. Guarde quantas vezes moveu para a direita. Se não parar naturalmente, está em loop infinito.
- Se parou e moveu para a direita 2 vezes, aceite.
- Se parou e moveu para a direita diferente de 2 vezes,