Notação

A notação gráfica para uma Máquina de Turing Determinística é:

Detalhando a imagem, note que ela possui:

• Uma fita, que corresponde ao principal dispositivo por ela operado. Serve como entrada, saída e memória da Máquina de Turing;

• Uma cabeça de leitura e escrita, também conhecida como unidade de controle, que corresponde à posição da fita sendo operada no momento. Ela pode e deve (exceto no modelo com Parada de Movimento, que a livra desta obrigação) se movimentar uma posição para a direita ou uma posição para a esquerda. No modelo que está sendo apresentado, a fita é limitada pela esquerda, mas ilimitada pela direita. Isto significa que não será possível se mover para a esquerda do limite.

• E uma função de transição, também conhecido por programa, a qual determina o comportamento da máquina, principalemte no que tange aos seguintes aspectos:

• O que será escrito;

• Para onde deve ser o movimento;

• Qual deve ser o próximo estado.

• Estas decisões são tomadas de acordo com o estado atual e com o símbolo lido.