Was ist das absolute Minimum an Anweisungen, die zum Erstellen eines vollständigen Prozessors von Turing erforderlich sind?

Ich habe eine allgemeine Vorstellung davon, wie der Prozessor mit Anweisungen umgeht, verbringe aber meine Zeit damit, hauptsächlich in Hochsprachen zu arbeiten. Vielleicht kann jemand, der näher am Eisen arbeitet, wertvolle Erkenntnisse liefern.

Angenommen, Programmiersprachen sind im Grunde genommen Abstraktionen auf sehr hoher Ebene des Befehlssatzes eines Prozessors. Was ist der grundlegendste Befehlssatz, der zum Erstellen einer vollständigen Maschine erforderlich ist?

Hinweis: Ich weiß nichts über die Vielfalt der Hardwarearchitekturen, gehe aber der Einfachheit halber davon aus, dass es sich um einen typischen Prozessor mit einer ALU (falls erforderlich) und einem Anweisungsstapel handelt. *

Es stellt sich heraus, dass Sie nur eine Anweisung benötigen , um eine Maschine zu bauen, die Turing-fähig ist. Diese Klasse von Maschinen, die nur eine Anweisung haben und vollständig sind, heißt One Instruction Set Computers oder auch Ultimate RISC .

Es gibt viele Möglichkeiten, etwas zu implementieren, in das man eine Turing-Maschine implementieren kann.

Bei Prozessoren ist wahrscheinlich das Registermaschinenmodell am besten geeignet . Das einfachste von diesen (in Bezug auf Symbole) ist das Multiband-Zwei-Symbol ( markund blank). Wenn Sie sich für etwas entscheiden, das nicht ganz so esoterisch ist, können Sie die Befehle inc(r), dec(r)und jz(r,z)(Sprung, wenn das Register rNull ist z) oder clr(r)(Löschen r) inc, je(i,j,z)(Sprung, wenn die Register i und j gleich dem Befehl z sind) verwenden.

Ich habe die Erwähnung einer Registriermaschine gesehen, die ist:

• inc (i, m) - Inkrementiere das Register i und gehe zu Zeile m
• jzdec (i, m1, m2) - Wenn das Register i 0 ist, gehe zu Zeile m, sonst dekrementiere i und gehe zu Zeile m2

Das ist auch komplett - es ist eine Minsky-Registermaschine, obwohl es andere Einschränkungen für die Daten auf dem Band gibt (es muss eine Gödel-Nummer sein, die den Zustand und nicht einzelne Register speichert).

Das ist es. Nichts mehr.

Warum werden diese Ultra Risc-Prozessoren nicht stattdessen verwendet? Es ist ein echtes Problem, einen Compiler für sie zu schreiben, und Sie geben viele andere Dinge auf, die der Prozessor tun kann. Es ist wirklich schön, ein bitweises zu haben andund addnicht zu versuchen, alles mit inkrementierenden Registern und Schleifen zu tun. Das ist die Basis einer bevorzugten Programmiersprache mit dem Titel Brainfuck, die 8 Anweisungen enthält.

• > Inkrementieren Sie den Datenzeiger
• < Dekrementieren Sie den Datenzeiger
• + Inkrementieren Sie die Daten am Datenzeiger
• - Dekrementieren Sie die Daten am Datenzeiger
• . Die Daten werden am Datenzeiger ausgegeben
• , Leseeingang, Speichern der Daten am Datenzeiger
• [Wenn die Daten am Zeiger Null sind, anstatt den Befehlszeiger um eins vorwärts zu bewegen, springen Sie vorwärts zum Befehl nach dem übereinstimmenden ]Befehl
• ]Wenn die Daten am Zeiger ungleich Null sind, anstatt den Befehlszeiger vorwärts zu bewegen, springen Sie zum Befehl nach dem übereinstimmenden ]Befehl zurück

Man kann Compiler für Brainfuck finden, obwohl es wirklich keinen Spaß macht, auch nur einfache Dinge darin zu machen. Es sei denn, Sie genießen die Frustration, die der Zweck der Sprache ist.

Verwandte Lesung:

• (Esolangs) Turing Tarpit
• Was macht eine Sprache Turing-complete? (für eine Programmiersprache)
• Warum ist FRACTRAN vollständig? (auf Gödel-Nummern-basierten Registern)

Ich vermute , dass Beitrag Maschine über die einfachste Form eines Turing-complete - Geräts ist. Sie benötigen einen bitadressierbaren Speicher, ein Adressregister, das auf die aktuelle Datenposition verweist, und fünf Anweisungen:

• Setzen Sie das Bit an der aktuellen Position.
• Setzen Sie das Bit an der aktuellen Position zurück.
• Zur nächsten Adresse gehen (Datenadressregister inkrementieren);
• Zur vorherigen Adresse gehen (Datenadressregister dekrementieren);
• Überprüfen Sie das Bit an der aktuellen Datenposition.

Ich denke nicht, dass es einfach ist, Hardware einfacher zu erfinden, obwohl es wahrscheinlich etwas noch Reduzierteres gibt.

Implementierungen

Diese Antwort konzentriert sich auf interessante Implementierungen von CPUs, Compilern und Assemblern mit einem Befehlssatz.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Kompiliert C-Code nur mit movx86-Anweisungen und zeigt auf sehr konkrete Weise, dass eine einzelne Anweisung ausreicht.

Die Vollständigkeit von Turing scheint in einem Artikel nachgewiesen worden zu sein: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

https://esolangs.org/wiki/Subleq :

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog und VHDL, Altera.
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C ++ Assembler und Emulator.

Siehe auch

/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

Was ist das absolute Minimum an Anweisungen, um einen Turing-Komplettprozessor zu erstellen?

Jörg W. Mittag sagte "Eins", aber wie wäre es mit Null?

Warum nehmen Sie an, dass ein "Prozessor" "Anweisungen" haben muss?

Eine Turing-Maschine ist ein Turing-Komplettprozessor und arbeitet nicht mit "Anweisungen" als solchen. Es hat Regeln , aber die Regeln sind keine Anweisungen, die aus einem Arbeitsspeicher abgerufen werden.

Als Alan Turing sich seine gleichnamige Maschine ausgedacht hatte, suchte er nach einem möglichst einfachen "Rechenmodell", um die Frage "Was ist berechenbar?" Mit mathematischen Methoden beantworten zu können.

Es würde Ihnen schwer fallen, eine Turing-äquivalente Maschine zu entwickeln, die einfacher ist als eine tatsächliche Turing-Maschine.

FWIW, der Prozessortyp, an den Sie denken - ein Prozessor, der Anweisungen aus dem Speicher abruft, sie decodiert und ausführt und mit Daten arbeitet, die im selben Speichersystem gespeichert sind - ist als Von Neumann-Architektur bekannt

https://en.wikipedia.org/wiki/Von_Neumann_architecture