Mathematica Eterna
Offener Zugang

Abstrakt

Reverse Engineering von Turingmaschinen und Einblicke in die Collatz-Vermutung.

John Nixon

In diesem Artikel habe ich meine frühere Arbeit [3] über kleine Turingmaschinen (TMs) erweitert, indem ich eine Methode entwickelt habe, um rekursive Definitionen der irreduziblen regulären Regeln (IRR) für eine TM zu erhalten, wenn keine expliziten Formeln dafür verfügbar sind. Dies wurde durch zwei Beispiele veranschaulicht. Das erste Beispiel wurde zufällig ausgewählt und das zweite Beispiel wurde entwickelt, um die Collatz-Vermutung zu simulieren. Die Analyse dieser TM auf der Grundlage ihrer IRR legte neue Ansätze nahe, die die Grundlage für einen Beweis dieser Vermutung bilden könnten. Die Methode beinhaltet das Rückwärtslaufen der TM von einem Konfigurationssatz (CS) aus. Dies erzeugt im Allgemeinen bei jedem Schritt einen Baum von CSs. Das Ziel besteht darin, CSs y zu finden, die von einer CS x aus erreichbar sind, die einfach das zu lesende Symbol und den Maschinenzustand angibt. Dies bedeutet, dass die CS y erreicht werden kann, indem man die Berechnung von x aus vorwärts fortsetzt, indem man bei Bedarf einige Symbole am Zeiger hinzufügt. Diese CSs bilden die Grundlage der LHSs der IRR.