Mathematica Eterna
Libre accès
ISSN: 1314-3344
ISSN: 1314-3344
John Nixon
Cet article est une étude ab initio des différentes manières de décrire le comportement de la machine de Turing (TM). Il montre comment les résultats d'une TM restreinte à une longueur finie de bande peuvent être utilisés pour accélérer tout calcul de TM. L'ensemble non redondant de ces règles est appelé règles de calcul régulières irréductibles (IRR) et un algorithme est décrit pour les générer pour toute TM pour une longueur de bande arbitraire. Cet algorithme a été implémenté en C++ tel qu'il est disponible gratuitement. Les exemples étudiés montrent que les IRR peuvent être en nombre fini ou infini. Pour plusieurs TM lorsqu'elles sont infinies, des formules récursives pour elles ont été trouvées et il est prévu que cela soit toujours possible. Ces formules ont été trouvées en examinant les IRR dans chaque exemple séparément et en les devinant correctement et en les prouvant par induction. Un tableau montrant quelles IRR suivent les autres en fonction du symbole suivant lu a été trouvé pour les exemples étudiés et donne de nombreuses informations sur le comportement de la TM. Il est prévu qu'il sera possible de cette manière d'analyser une TM universelle pour découvrir comment fonctionne le cycle d'interprétation.