Eine kleine C-ähnliche Sprache, die Turingmaschinen simulieren können

Ich suche eine kleine Sprache, die hilft, die Schüler davon zu überzeugen, dass Turingmaschinen ein ausreichend allgemeines Rechenmodell sind. Das heißt, eine Sprache, die den gewohnten Sprachen ähnelt, aber auch auf einer Turingmaschine leicht zu simulieren ist.

Papadimitriou verwendet RAM-Maschinen für diesen Job, aber ich befürchte, dass es für viele Studenten zu wenig überzeugend wäre, etwas Seltsames (als Turing-Maschine) mit einer anderen seltsamen Sache (im Grunde eine Assemblersprache) zu vergleichen.

Vorschläge sind sehr willkommen (insbesondere, wenn sie empfohlene Literatur enthalten).

• Wenn Ihre Schüler eine funktionale Programmierung durchgeführt haben, ist der schönste Ansatz, den ich kenne, mit dem untypisierten Lambda-Kalkül zu beginnen und ihn dann mithilfe des Klammerabstraktionssatzes in SKI-Kombinatoren zu übersetzen. Anschließend können Sie mithilfe der Sätze und zeigen, dass Turing-Maschinen eine partielle kombinatorische Algebra bilden , und so die SKI-Kombinatoren interpretieren.u t $smn$$utm$

  Ich bezweifle, dass dies der einfachste mögliche Ansatz ist, aber ich mag, wie er auf einigen der grundlegendsten Theoreme der Berechenbarkeit beruht (die Sie möglicherweise aus anderen Gründen behandeln möchten).

  Es scheint, dass Andrej Bauer vor einigen Monaten eine ähnliche Frage zu Mathoverflow beantwortet hat .

• Wenn Sie auf eine C-ähnliche Sprache eingestellt sind, ist Ihr Pfad viel rauer, da sie eine ziemlich komplizierte Semantik haben - das müssen Sie

  1. Zeigen Sie, dass Turing-Maschinen gleichzeitig einen Stapel und einen Haufen simulieren können, und
  2. Zeigen Sie, wie Variablen mit einem Stapel implementiert werden können, und
  3. Zeigen Sie, dass Prozeduraufrufe mit einem Stapel implementiert werden können.

  Dies ist ehrlich gesagt ein Großteil des Inhalts einer Compiler-Klasse.

Mein Professor für Theorie der Comp im Grundstudium begann mit dem Nachweis, dass eine Turing-Maschine mit einem Band eine Turing-Maschine mit mehreren Bändern implementieren kann. Dies behandelt die Variablendeklaration: Wenn ein Programm sechs Variablendeklarationen hat, kann es einfach auf einer Turing-Maschine mit sieben Bändern implementiert werden (ein Band für jede Variable und ein "Register" -Band, um Aufgaben wie Arithmetik und Gleichheitsprüfung zwischen diesen auszuführen Bänder). Anschließend zeigte er, wie grundlegende FOR- und WHILE-Schleifen implementiert werden, und zu diesem Zeitpunkt hatten wir eine grundlegende Turing-vollständige C-ähnliche Sprache. Ich fand es sowieso befriedigend.

Ich denke gerade darüber nach, wie ich mich davon überzeugen kann, dass Turing-Maschinen ein allgemeines Rechenmodell sind. Ich stimme zu, dass die Standardbehandlung der Church-Turing-These in einigen Standardlehrbüchern, z. B. Sipser, nicht sehr vollständig ist. Hier ist eine Skizze, wie ich von Turing-Maschinen zu einer erkennbareren Programmiersprache gelangen könnte.

Betrachten Sie eine blockstrukturierte Programmiersprache mit ifund while-Anweisungen mit nicht rekursiv definierten Funktionen und Unterprogrammen, mit benannten booleschen Zufallsvariablen und allgemeinen booleschen Ausdrücken sowie mit einem einzelnen unbegrenzten booleschen Array tape[n]mit einem ganzzahligen Arrayzeiger n, der inkrementiert oder dekrementiert werden kann, n++oder n--. Der Zeiger nist anfänglich Null und das Array tapeist anfänglich alle Null. Diese Computersprache kann also C-ähnlich oder Python-ähnlich sein, ist jedoch in ihren Datentypen sehr begrenzt. Tatsächlich sind sie so begrenzt, dass wir nicht einmal die Möglichkeit haben, den Zeiger nin einem booleschen Ausdruck zu verwenden. Vorausgesetzt, dasstapeIst nur unendlich rechts, können wir einen Zeiger-Unterlauf als "Systemfehler" deklarieren, falls dieser njemals negativ ist. Unsere Sprache hat auch eine exitAnweisung mit einem Argument, um eine boolesche Antwort auszugeben.

Dann ist der erste Punkt, dass diese Programmiersprache eine gute Spezifikationssprache für eine Turing-Maschine ist. Sie können leicht erkennen, dass der Code mit Ausnahme des Bandarrays nur endlich viele mögliche Zustände aufweist: den Zustand aller deklarierten Variablen, die aktuelle Ausführungszeile und seinen Unterprogrammstapel. Letzteres hat nur eine begrenzte Menge an Zustand, da rekursive Funktionen nicht zulässig sind. Sie können sich einen "Compiler" vorstellen, der aus einem Code dieses Typs eine "tatsächliche" Turing-Maschine erstellt, aber die Details dazu sind nicht wichtig. Der Punkt ist, dass wir eine Programmiersprache mit ziemlich guter Syntax, aber sehr primitiven Datentypen haben.

Der Rest der Konstruktion besteht darin, dies in eine lebenswertere Programmiersprache mit einer endlichen Liste von Bibliotheksfunktionen und Vorkompilierungsstufen umzuwandeln. Wir können wie folgt vorgehen:

1. Mit einem Precompiler können wir den booleschen Datentyp auf ein größeres, aber endliches Symbolalphabet wie ASCII erweitern. Wir können davon ausgehen, dass dies tapeWerte in diesem größeren Alphabet annimmt. Wir können eine Markierung am Anfang des Bandes hinterlassen, um ein Unterlaufen des Zeigers zu verhindern, und eine bewegliche Markierung am Ende des Bandes, um zu verhindern, dass das TM versehentlich auf dem Band bis ins Unendliche läuft. Wir können beliebige binäre Operationen zwischen Symbolen und Konvertierungen in boolesche for- ifund whileAnweisungen implementieren . ( ifKann tatsächlich auch mit implementiert werden while, wenn es nicht verfügbar wäre.)

2. $k$$k$$i$$i$$k$

3. Wir bezeichnen ein Band als symbolwertigen "Speicher" und die anderen als vorzeichenlose, ganzzahlige "Register" oder "Variablen". Wir speichern die ganzen Zahlen in Little-Endian-Binärdateien mit Terminierungsmarkern. Wir implementieren zuerst eine Kopie eines Registers und eine binäre Dekrementierung eines Registers. In Kombination mit dem Inkrementieren und Dekrementieren des Speicherzeigers können wir eine Direktzugriffssuche des Symbolspeichers implementieren. Wir können auch Funktionen schreiben, um die binäre Addition und Multiplikation von ganzen Zahlen zu berechnen. Es ist nicht schwer, eine binäre Additionsfunktion mit bitweisen Operationen und eine Funktion zum Multiplizieren mit 2 mit Linksverschiebung zu schreiben. (Oder wirklich Rechtsverschiebung, da es Little-Endian ist.) Mit diesen Grundelementen können wir eine Funktion schreiben, um zwei Register unter Verwendung des langen Multiplikationsalgorithmus zu multiplizieren.

4. Mit der Formel können wir das Speicherband von einem eindimensionalen Symbolarray symbol[n]in ein zweidimensionales Symbolarray umorganisieren . Wir können jetzt jede Zeile des Speichers verwenden, um eine vorzeichenlose Ganzzahl in Binärform mit einem Abschlusssymbol auszudrücken und einen eindimensionalen Speicher mit wahlfreiem Zugriff und ganzzahligem Wert zu erhalten . Wir können das Lesen aus dem Speicher in ein ganzzahliges Register und das Schreiben aus einem Register in den Speicher implementieren. Viele Funktionen können jetzt mit Funktionen implementiert werden: Vorzeichen- und Gleitkomma-Arithmetik, Symbolzeichenfolgen usw.symbol[x,y]n = (x+y)*(x+y) + ymemory[x]

5. Nur eine weitere grundlegende Funktion erfordert unbedingt einen Precompiler, nämlich rekursive Funktionen. Dies kann mit einer Technik erfolgen, die häufig zur Implementierung interpretierter Sprachen verwendet wird. Wir weisen jeder übergeordneten rekursiven Funktion eine Namenszeichenfolge zu und organisieren den Code auf niedriger Ebene in einer großen whileSchleife, die einen Aufrufstapel mit den üblichen Parametern verwaltet: dem Aufrufpunkt, der aufgerufenen Funktion und einer Liste von Argumenten.

Zu diesem Zeitpunkt verfügt die Konstruktion über genügend Funktionen einer höheren Programmiersprache, sodass weitere Funktionen eher das Thema von Programmiersprachen und Compilern als die CS-Theorie sind. Es ist auch schon einfach, einen Turing-Maschinensimulator in dieser entwickelten Sprache zu schreiben. Es ist nicht gerade einfach, aber sicherlich Standard, einen Self-Compiler für die Sprache zu schreiben. Natürlich benötigen Sie einen äußeren Compiler, um das äußere TM aus einem Code in dieser C- oder Python-ähnlichen Sprache zu erstellen, aber das kann in jeder Computersprache erfolgen.

Beachten Sie, dass diese skizzierte Implementierung nicht nur die Church-Turing-These der Logiker für die rekursive Funktionsklasse unterstützt, sondern auch die erweiterte (dh polynomielle) Church-Turing-These, wie sie für deterministische Berechnungen gilt. Mit anderen Worten, es hat einen Polynom-Overhead. Wenn wir eine RAM-Maschine oder (mein persönlicher Favorit) ein Tree-Tape TM erhalten, kann dies für die serielle Berechnung mit RAM-Speicher auf polylogarithmischen Overhead reduziert werden.

Der LLVM-Compiler ermöglicht es, eine neue Architektur ziemlich einfach "einzufügen". Sie nennen dieses Schreiben ein neues Back-End und geben detaillierte Anweisungen und Beispiele dafür. Ich vermute, dass Sie in Bezug auf den Arbeitsspeicher durch einige Bereiche springen müssen, wenn Sie nicht auf eine RAM-Turing-Maschine abzielen möchten, aber dies ist definitiv machbar, da ich eine Reihe von Projekten gesehen habe, die LLVM generieren VHDL oder andere sehr unterschiedliche Maschinensprachen.

Dies hätte den interessanten Effekt, dass ein hochmoderner Optimierungs-Compiler (in vielerlei Hinsicht ist LLVM weiter fortgeschritten als GCC) Code für eine Turing-Maschine generiert.

Ich bin nicht in der cs-Theorie, aber ich habe etwas, das nützlich sein könnte. Ich habe einen anderen Ansatz gewählt. Ich habe einen einfachen Prozessor entworfen, der direkt mit einer kleinen Teilmenge von C programmierbar ist. Es gibt KEINEN Assembler-Code, nur C-ähnlichen Code. Sie können dasselbe Tool verwenden, das ich verwendet habe, und diesen Prozessor modifizieren, um Ihren Turing-Maschinensimulator zu entwerfen. Ich habe 4 Tage gebraucht, um diesen Prozessor zu entwerfen, zu simulieren und zu testen, also ein paar Anweisungen! Mit den von mir verwendeten Tools konnte ich sogar echten synthetisierbaren VHDL-Code generieren. Es ist ein wirklich funktionierender Prozessor.

So sieht ein Programm aus:

Hier ist ein Bild des Prozessors mit diesen Tools :.

Die Tools "Novakod Studio" verwenden eine Hardware-Beschreibungssprache auf hoher Ebene. Als Beispiel hier der Code des Programmzählers: Genug gesprochen, wenn jemand interessiert ist, hier sind die öffentlichen Informationen, um mich zu kontaktieren: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Luc

Wie wäre es, wenn Sie die Idee des Benutzers GMB hier aufgreifen (Turing-Maschine mit einem Band kann eine Turing-Maschine mit N Bändern simulieren, indem Sie die N Bänder auf ein einzelnes Band verschachteln und eines dieser Bänder lesen, indem Sie N Stellen gleichzeitig überspringen, eine Turing Maschine mit N Bändern kann implementieren ...) und ein Turing-Maschinenprogramm schreiben, das eine vereinfachte RAM-Maschine implementiert. Die RAM-Maschine könnte tatsächlich eine vereinfachte, echte CPU mit verfügbarem LLVM- oder GCC-Backend sein. Dann kann das GCC / LLVM zum Kreuzkompilieren eines C-Programms für diese CPU verwendet werden, und das Turing-Maschinenprogramm, das die RAM-Maschine simuliert, führt die RAM-Maschinensimulation aus, indem die simulierte RAM-Maschine die GCC / LLVM-Ausgabe ausführen lässt. Die Implementierung der Turing-Maschine kann ein sehr einfacher C-Code sein, der in eine kleine C-Datei passt.

Was die RAM-Maschine betrifft, dann gibt es ein Demo-Projekt, bei dem eine 32-Bit-CPU von einem 8-Bit-Mikrocontroller simuliert wird und die simulierte 32-Bit-CPU Linux bootet. Langsam wie die Hölle, aber laut dem Autor Dmitry Grinberg hat es funktioniert. Vielleicht ist die Zylin-CPU (GitHub-Benutzer zylin) eine gute Wahl für die simulierbare RAM-Maschine. Ein weiterer Kandidat für eine RAМ-Maschine könnte das ProjectOberon dot com von Niklaus Wirth sein .

(Der "Punkt" und "com" in meinem Text sind darauf zurückzuführen, dass ich gerade, 2015_10_21, mein Konto bei cstheory.stackexchange registriert habe und die Web-App trotz der Tatsache nicht mehr als 2 Links für Anfänger zulässt dass sie automatisch von meinen anderen Stackexchange-Konten sehen können, dass ich vielleicht dumm bin, aber kein Troll bin.)