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.
Nach http://de.wikipedia.org/wiki/Turing-Maschine#Formale_Definition gibt es max
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.
A. K. schrieb: > http://en.wikipedia.org/wiki/One_instruction_set_computer Wenn man's drauf anlegt, wäre eigentlich nur die Transport-Triggered-Architecture ein OISC, die anderen fassen mehrere Operationen in einem Befehl zusammen... ;)
:
Bearbeitet durch User
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.
:
Bearbeitet durch User
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 :)
Das Vorzeichenbit (also eher (2<<vz)) addieren und damit toggeln geht.
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
:
Bearbeitet durch User
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.