Mathematica Eterna
Libre accès

Abstrait

Ingénierie inverse des machines de Turing et aperçu de la conjecture de Collatz.

John Nixon

Dans cet article, j'ai étendu mes travaux antérieurs [3] sur les petites machines de Turing (TM) en développant une méthode permettant d'obtenir des définitions récursives des règles régulières irréductibles (IRR) pour une TM lorsque des formules explicites pour elles ne peuvent pas être obtenues. Ceci a été illustré par deux exemples. Le premier exemple a été choisi au hasard et le second exemple a été conçu pour simuler la conjecture de Collatz. L'analyse de cette TM basée sur son IRR a suggéré de nouvelles approches qui pourraient servir de base à une preuve de cette conjecture. La méthode consiste à exécuter la TM à rebours à partir d'un ensemble de configuration (CS). Cela produit en général un arbre de CS à chaque étape. L'objectif est de trouver les CS y qui sont accessibles à partir d'un CS x qui spécifie simplement le symbole sur le point d'être lu et l'état de la machine. Cela signifie qu'en suivant le calcul vers l'avant à partir de x en ajoutant des symboles si nécessaire au pointeur, le CS y peut être atteint. Ces CS forment la base des LHS de l'IRR.