Minimal-Befehlssatz vor einem Problem mit einem Computerprogramm

Question

Jahren zu lösen, ich habe gehört, dass jemand im Begriff war, zu zeigen, dass jedes Computer-Programm mit nur drei Befehlen gelöst werden könnte:

• Zuordnung
• Conditional
• Loop

Bitte ich würde gerne Ihre Meinung hören. Ich meine, jeden Algorithmus als Computerprogramm darzustellen. Stimmst du dem zu?

Answer 1

Keine Notwendigkeit. Der minimale theoretische Computer benötigt nur eine Anweisung. Sie heißen One Instruction Set Computers (OISC for short, kinda like the ultimate RISC).

Es gibt zwei Arten. Die erste ist eine theoretisch "reine" Befehlsmaschine, in der die Anweisung wirklich wie eine normale Anweisung in normalen CPUs funktioniert. Die Anweisung lautet normalerweise:

subtract and branch if less than zero 

oder Variationen davon. Die wikipedia article haben Beispiele, wie diese einzelne Anweisung verwendet werden kann, um Code zu schreiben, der andere Anweisungen emuliert. Der zweite Typ ist nicht theoretisch rein. Es ist die transfer triggered architecture (Wikipedia wieder, sorry). Diese Architekturfamilie wird auch als Move-Maschine bezeichnet und ich habe sie selbst entworfen und gebaut.

Einige betrachten verschieben Maschinen betrügen, da die Maschine tatsächlich alle regulären Anweisungen haben nur, dass sie Speicher zugeordnet sind, anstatt Teil des Opcodes. Aber Move-Maschinen sind nicht nur theoretisch, sie sind praktisch (wie ich schon sagte, habe ich selbst gebaut). Es gibt sogar eine im Handel erhältliche Familie von CPUs, die von Maxim gebaut wurden: MAXQ. Wenn Sie sich den MAXQ-Befehlssatz anschauen (sie nennen ihn Übertragungssatz, da es wirklich nur einen Befehl gibt, den ich normalerweise als Registersatz bezeichne), werden Sie sehen, dass die MAXQ-Assemblierung eher wie eine standardmäßige akkumulatorbasierte Architektur aussieht.

Answer 2

Der Minimalsatz ist ein einzelner Befehl, aber Sie haben ein passendes ein, zum Beispiel wählen - One instruction set computer

Als ich studierte, wir einen solchen „Computer“ verwendet faktorielles zu berechnen, nur eine einzige Anweisung verwendet:

 
SBN - Subtract and Branch if Negative: 
SBN A, B, C 

Bedeutung:

if((Memory[A] -= Memory[B]) < 0) goto C 
// (Wikipedia has a slightly different definition) 

Answer 3

Dies ist eine Folge der Turing Completeness ist, das ist etwas, das viele Jahrzehnt gegründet wurde s vor.

Alan Turing, der berühmte Computerwissenschaftler, bewies, dass jede berechenbare Funktion mit einem Turing Machine berechnet werden konnte. Eine Turingmaschine ist ein sehr einfaches theoretisches Gerät, das nur wenige Dinge kann. Er kann auf ein Band (dh Speicher) lesen und schreiben, einen internen Zustand beibehalten, der durch den aus dem Speicher gelesenen Inhalt geändert wird, und den internen Zustand und die letzte gelesene Speicherzelle verwenden, um zu bestimmen, in welche Richtung das Band bewegt werden soll Speicherzelle.

Die Operationen Zuweisung, Bedingung und Schleife reichen aus, um eine Turing-Maschine zu simulieren. Das Lesen und Schreiben von Speicher und das Aufrechterhalten des Zustands erfordert eine Zuweisung.Das Ändern der Bandrichtung basierend auf dem Status und dem Speicherinhalt erfordert Bedingungen und Schleifen. "Loops" sind tatsächlich etwas höher als das, was tatsächlich benötigt wird. Alles was wirklich benötigt wird ist, dass der Programmablauf irgendwie zurückspringen kann. Dies bedeutet, dass Sie Schleifen erstellen können, wenn Sie möchten, aber die Sprache muss kein explizites Schleifenkonstrukt haben.

Da diese drei Operationen die Simulation einer Turing-Maschine ermöglichen und eine Turing-Maschine in der Lage ist, jede berechenbare Funktion zu berechnen, ist jede Sprache, die diese Operationen bereitstellt, auch in der Lage, jede berechenbare Funktion zu berechnen.

Edit: Und wie andere Beantworter darauf hingewiesen haben, müssen diese Operationen nicht diskret sein. Sie können eine einzelne Anweisung erstellen, die alle drei dieser Dinge (Zuweisen, Vergleichen und Verzweigen) so ausführt, dass sie eine Turing-Maschine selbst simulieren kann.

Answer 4

1964 Bohm und Jacopini veröffentlichten eine paper, in dem sie gezeigt, dass alle Programme im Hinblick auf die nur drei Kontrollstrukturen geschrieben werden könnten: die Sequenzstruktur, die Selektionsstruktur und die Wiederholungsstruktur.

Answer 5

Implementations

Diese Antwort auf interessante Implementierungen von einzelnen Befehlssatz CPUs, Compiler und Montierer konzentrieren.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Kompiliert Code C nur mov x86-Instruktionen verwenden, in ganz konkret zeigen, dass ein einzelner Befehl genügt.

Die Turing Vollständigkeit scheint in einem Papier bewährt zu haben: 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. Vielleicht hat das Projekt ein Backend, aber ich kann es nicht benutzen: https://github.com/purisc-group/purisc/issues/5
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C++ - basierter Assembler und Emulator.

Siehe auch

https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

Answer 6

Programmierer mit Haskell könnte argumentieren, dass Sie nur die Contional und Schleife, da Zuweisungen benötigen, und wandelbaren Zustand, existieren nicht in Haskell.