Mathematica Eterna
Acesso livre
ISSN: 1314-3344
ISSN: 1314-3344
John Nixon
Este artigo é uma investigação ab initio sobre formas de descrever o comportamento da Máquina de Turing (TM). É mostrado como os resultados de uma TM restrita a um comprimento finito de fita podem ser utilizados para acelerar qualquer cálculo da TM. O conjunto não redundante de tais regras é referido como regras regulares (de computação) irredutíveis (TIR) e é descrito um algoritmo para as gerar para qualquer TM para um comprimento de fita arbitrário. Este algoritmo foi implementado em C++ e está disponível gratuitamente. Os exemplos estudados mostram que a TIR pode ser em número finito ou infinito. Para várias TM’s quando são infinitas, foram encontradas fórmulas recursivas para as mesmas e espera-se que isso seja sempre possível. Estas fórmulas foram encontradas examinando a TIR em cada exemplo separadamente e adivinhando-a corretamente e provando-a por indução. Uma tabela que mostra quais as TIR que se seguem a outras dependendo do próximo símbolo lido, foi encontrada para os exemplos estudados e fornece muita informação sobre o comportamento da TM. Prevê-se que desta forma será possível analisar uma TM universal para descobrir como funciona o ciclo de interpretação.