Moin,
in einer Vorlesung haben wir mal gelernt, dass eine Programmiersprache
eine sehr geringe Anzahl von Anweisungen braucht, um Turing-vollständig
zu sein. Ich glaube, dass es sechs Befehle waren. Stimmt das und welche
Befehle könnten das sein? Zwei waren, soweit ich mich erinnere ein
Additionsbefehl und ein Sprungbefehl. Dazu kommt noch ein Subtraktions-
oder ein Negierbefehl.
Ich weiß, dass es mehrere Möglichkeiten gibt, aber welche wären das?
Brainfuсk hat acht Befehle und ist Turing-vollständig, also ist die
maximale benötigte Anzahl eben acht.
verschiedene Zustandsübergänge im endlichen Automaten, die kann man als
Befehle auffassen, wobei
Q = Zustände im Automaten
Γ = Bandalphabet
Das wäre dann sozusagen die minimale Menge an Befehlen.
Arc Net schrieb:> Wenn man's drauf anlegt, wäre eigentlich nur die> Transport-Triggered-Architecture ein OISC,
Gibt es: MaxQ2000.
> die anderen fassen mehrere Operationen in einem Befehl zusammen... ;)
Gefragt war nach Befehlen, nicht nach internen Operationen.
Compare-and-branch ist ein auch bei RISCs gebräuchlicher Befehl.
Ok, schonmal danke für die Antworten.
Die sind aber schon eher theoretisch und die erste Antwort überschreitet
meine mathematischen Kenntnisse ;-) Deshalb stelle ich die Frage mal
anders: Auf welche Befehle kann man einen 'normalen'
Assemblerbefehlssatz kürzen, um noch Turing-vollständig zu sein. Um die
Diskussion über 'normal' zu vermeiden, nenne ich mal den AVR- oder PIC-
(von mir aus auch X86/X64, wobei der wieder CISC ist) Befehlssatz.
Naja, den hier
http://en.wikipedia.org/wiki/One_instruction_set_computer#Subtract_and_branch_if_not_equal_to_zero
beschriebenen SBNZ-Befehl kannst du aus den AVR-Befehlen LD, ST, SUB und
BRNE zusammensetzen. Ein auf diese 4 Befehle abgespeckter AVR wäre damit
Turing-vollständig.
Mit weniger als 4 AVR-Befehlen ist dies vermutlich nicht möglich, da man
mindestens einen Lese- und einen Schreibbefehl für den RAM, dazu noch
einen Arithmetik- und einen bedingten Sprungbefehl benötigt. Da es diese
vier Befehlstypen nicht in Kombination gibt, wird ein Exemplar von jedem
benötigt.
Subtraktion ist nicht notwendig, da sie als Sonderform der Addition
nachgebildet werden kann.
IMHO ist man bereits Turing vollständig, wenn man kann
* aus dem Speicher lesen und in den Speicher schreiben
* Addition (wobei ein Inkrement bereits genügen müsste)
* Vergleich (auf 0)
* Sprung, bzw. bedingter Sprung.
Ich denke das müsste genügen. Alles andere kann dann darauf aufbauend
implementiert werden.
Karl Heinz schrieb:> Subtraktion ist nicht notwendig, da sie als Sonderform der Addition> nachgebildet werden kann.
Wie geht das?
Aus Subtraktionen lässt sich relativ leicht eine Addition zaubern, aber
für die umgekehrte Richtung fällt mir spontan nichts ein. Vielleicht
habe ich aber auch nur gerade ein Brett vor dem Kopf :)
Yalu X. schrieb:> Wie geht das?>> Aus Subtraktionen lässt sich relativ leicht eine Addition zaubern, aber> für die umgekehrte Richtung fällt mir spontan nichts ein. Vielleicht> habe ich aber auch nur gerade ein Brett vor dem Kopf :)
Ah, richtig. Anders rum.
In Douglas Hpftstters 'Gödel Escher Bach' ist das irgendwo von der Pieke
auf durchexerziert.
Thomas Klima schrieb:> Das Vorzeichenbit (also eher (2<<vz)) addieren und damit toggeln geht.
Das geht aber nur dann, wenn die Zahlen nicht im Zweierkomplement,
sondern als Betrag und Vorzeichen dargestellt werden. Dann wird es aber
schwierig bis unmöglich, bspw. ein bitweises NOT zu berechnen.
Dussel schrieb:> Auf welche Befehle kann man einen 'normalen'> Assemblerbefehlssatz kürzen, um noch Turing-vollständig zu sein. Um die> Diskussion über 'normal' zu vermeiden, nenne ich mal den AVR- oder PIC-> (von mir aus auch X86/X64, wobei der wieder CISC ist) Befehlssatz.
MOV (x86) reicht, allgemeiner "Load Constant", "Load Indexed" und "Store
Indexed". Letztere beide dürfen auch so weit eingeschränkt sein, dass
man damit nur auf eine gerade Adresse oder ihre ungerade Folgeadresse
schreiben kann. Wenn man von endlichem Speicher ausgeht und ein Programm
mit Endlosschleifen schreiben möchte braucht man zudem noch einen
unbedingten Sprungbefehl.
Paper dazu gibts da: http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
Eine eigene Frage?
Dieser Thread ist über 12 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
