Ciências da computação dia 188

Maquina de Turing

• automato capaz de representar qualquer algoritmo computacional
• é um AFD
• não precisa de transições para todos os estados
• ele começa a ler a fita a partir de um símbolo inicial (como um δ)
• cada transição tem 3 parâmetros(leia -> escreva, vá)
• vá pode ser direita ou esquerda
• quando você não quer escrever outro valor, você coloca o mesmo (A -> A)
• pense em uma fita infinita, do qual uma cabeça de leitura pode ler, modificar valores e ir para a direita ou esquerda

nesse caso, d representa δ e 3 representa ε