Minimaler Befehlssatz für Turing-Vollständigkeit

http://en.wikipedia.org/wiki/One_instruction_set_computer

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... ;)

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.

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