Mathematica Eterna
Offener Zugang

Abstrakt

Methoden zum Verständnis von Turingmaschinenberechnungen

John Nixon

Dieser Artikel ist eine Ab-initio-Untersuchung von Möglichkeiten zur Beschreibung des Verhaltens von Turingmaschinen (TM). Es wird gezeigt, wie Ergebnisse für eine TM, die auf eine endliche Bandlänge beschränkt ist, verwendet werden können, um jede TM-Berechnung zu beschleunigen. Der nicht redundante Satz solcher Regeln wird als irreduzible reguläre (Berechnungs-)Regeln (IRR) bezeichnet, und es wird ein Algorithmus beschrieben, um sie für jede TM für eine beliebige Bandlänge zu generieren. Dieser Algorithmus wurde in C++ implementiert, da es frei verfügbar ist. Die untersuchten Beispiele zeigen, dass die IRR entweder endlich oder unendlich groß sein können. Für mehrere TMs, wenn sie unendlich sind, wurden rekursive Formeln für sie gefunden, und es wird erwartet, dass dies immer möglich ist. Diese Formeln wurden gefunden, indem die IRR in jedem Beispiel separat untersucht und richtig erraten und durch Induktion bewiesen wurden. Für die untersuchten Beispiele wurde eine Tabelle gefunden, die zeigt, welche IRR anderen folgen, abhängig vom nächsten gelesenen Symbol, und sie gibt viele Informationen über das TM-Verhalten. Es wird erwartet, dass es auf diese Weise möglich sein wird, eine universelle TM zu analysieren, um herauszufinden, wie der Interpretationszyklus funktioniert.