Padrões de projeto clássicos para máquinas de Turing
Técnica de Marcação (Check-off)
Como funciona: Você lê um caractere, substitui por um símbolo especial (como X ou Y) para “riscá-lo” da lista, e vai procurar o caractere correspondente lá na frente.
Quando usar: Excelente para linguagens que exigem contagem pareada, como o clássico (mesma quantidade de ‘a’ e ‘b’).
O Vai-e-Vem (Sweeping / Shuttling)
Como funciona: O cabeçote lê a fita da esquerda para a direita executando uma ação (como cortar metade dos zeros), chega no final, e um estado exclusivo tem a única função de rebobinar tudo para a esquerda para recomeçar.
Quando usar: Como vimos no seu exercício de , é ideal para problemas de divisão, multiplicação ou quando é preciso reavaliar a palavra inteira em múltiplos “passes”.
Memória Finita no Estado (State Memorization)
Como funciona: Você cria “caminhos paralelos” no seu diagrama de estados para lembrar qual foi a última letra lida. Por exemplo: se leu a, vai para o ramo de estados superior; se leu b, vai para o ramo inferior.
Quando usar: Quando você precisa carregar uma informação da ponta esquerda da fita lá para a ponta direita, mas não quer escrever nada na fita. O “estado” atua como uma variável temporária que guarda um único caractere.
Uso de Delimitadores
Como funciona: Inserir símbolos artificiais (como $) nas pontas da palavra original para que a máquina saiba exatamente onde é o começo e o fim do “território seguro” de dados, evitando que ela se perca nos espaços em branco infinitos.