redundanzfreier Befehlssatz

http://www.greenarraychips.com/home/documents/greg/PB003-110412-F18A.pdf

Nunja. Du müsstest das vielleicht aus einzelnen gates aufbauen? Aber im 
Grunde brauchst du irgendwas wie einen mathematischen Beweis, dass eine 
beste Lösung existiert. Das hört sich nach einem Jahrhundertproblem an.

http://de.wikipedia.org/wiki/Vier-Farben-Satz

Meiner Meinung nach einzige (theoretische) Möglichkeit:
Es gibt für jedes Problem einen Befehl und es können nicht mehrere 
Befehle verkettet werden.
sonst kann man immer mehrere Programme finden, die genau das gleiche 
Ergebnis liefern.

Stefan Helmert schrieb:
> Interessant wäre es doch, wenn man eine Architektur/Befehlssatz finden
> würde, bei dem immer nur ein einziges Programm zur Realisierung einer
> Aufgabe gefunden werden kann. Das Programm ist dabei immer optimal. Es
> kann nicht optimiert werden, weder in Geschwindigkeit noch
> Speicherbedarf.
>
> Wie könnte so etwas aussehen?

So etwas kann für eine Turing-mächtige Maschine nicht existieren. Gäbe 
es eine Sprache, die dies darstellen könnte, wäre über die Reduktion des 
Äquivalenzproblems auch das Halteproblem gelöst.
Eine Entscheidung des Halteproblems ist jedoch bewiesener Maßen nicht 
auf der Menge aller Turingmaschinen möglich. (siehe Diagonalsprache)

Du müsstest also schon die Möglichkeiten deiner Maschine stark 
einschränken, damit es so etwas geben kann.

Der TO sollte wissen, dass er sich in unbestimmtes Terrain begibt. Viele 
Mathematiker sind schon dort verlorengegangen und sind verrückt 
geworden.

Markus W. schrieb:
> hmmm schrieb:
>> Meiner Meinung nach einzige (theoretische) Möglichkeit:
>> Es gibt für jedes Problem einen Befehl und es können nicht mehrere
>> Befehle verkettet werden.
>> sonst kann man immer mehrere Programme finden, die genau das gleiche
>> Ergebnis liefern.
>
> Das ist eine ausgezeichnete Idee!
> Am besten, es gibt auch für die automatische Suche nach der vom
> Thread-Ersteller gewünschten Rechnerarchitektur einen solchen Befehl,
> dann haben wir das Problem gelöst. :-)

Das bringt mich darauf, dass die Suche eindeutig bestimmen muss welches 
Problem es ist -> Äquivalente Probleme könnten das ganze wieder 
zerstören.

Hallo,

was den nicht redundanten Befehlssatz angeht, ist man bei der 
Turingmaschine mit dem Alfabet 0,1 richtig, die kennt nur die Befehle:

Stehenbleiben, 0 Schreiben, neuer Zustand n
Stehenbleiben, 1 Schreiben, neuer Zustand n
nach Links, 0 Schreiben, neuer Zustand n
nach Links, 1 Schreiben, neuer Zustand n
nach Rechts, 0 Schreiben, neuer Zustand n
nach Rechts, 1 Schreiben, neuer Zustand n

das ist minimal und nicht redundand. Bewiesen wurden die Sätze
"Alles was berechenbar ist, ist durch eine Turingmaschine berechenbar" 
und
"Alles was nicht durch eine Turingmaschoine berechenbar ist, kann 
überhaupt nicht berechnet werden".

M.a.W. jedes sinnvolle Rechenprogramm lässt sich auch auf einer 
Turingmaschine programmieren und ausführen, was bedeutet, der obige 
Befehlssatz reicht für alle Programme aus. Über die Eindeutigkeit ist 
damit allerdings nichts ausgesagt, dass ein Programm mit minimalem 
Befehlssatz nur auf eine einzige Art realisiert werden kann ist meiner 
Meinung nach auch von vornherein falsch.

Allerings ist die ganze Frage etwas spät dran, Alan Turing hat die 
Turingmaschine 1920 definiert. Wenn der Fragesteller noch ein paar Jahre 
gewartet hätte, könnte die Antwort hundertjährigen Geburtstag feiern.

Reinhard Kern

Sowas wie 2*1 oder 1*2?
g

Reinhard Kern schrieb:
> das ist minimal und nicht redundand

Natürlich ist das redundant im Sinne des TO:

"bei dem immer nur ein einziges Programm zur Realisierung einer
Aufgabe gefunden werden kann."
das kann ich bei deiner

tja schrieb:
> Viele
> Mathematiker sind schon dort verlorengegangen und sind verrückt
> geworden.

Turing wurde psychiatrisch behandelt - allerdings wegen Homosexualität. 
Das ist sicher nicht das was du meinst.

Gruss Reinhard

tja schrieb:
> Viele
> Mathematiker sind schon dort verlorengegangen und sind verrückt
> geworden.


Berufsrisiko.
Ham die eigentlich für den Fall ne Berufsunfähigkeitsversicherung?
;-)

Vieleicht ist das die Lösung?

Hier noch das fehlende l: l

solange A+B das gleiche ist wie B+A und C*D das gleiche wie D*C wird 
sich die Vision des TO wohl nicht realisieren lassen.....

A. K. schrieb:
> Eher Kurt Gödel. Der hatte auch mehr Grund dazu gegeben als Turing.
> Immerhin hatte er Hilberts Traum einer perfekten Mathematik gründlich
> den Boden weggezogen.

Ja da sind die Weisskittel wohl zu spät gekommen. Früher war Mathematik 
viel einfacher und vor allem hoffnungsvoller.

Tom schrieb:
> solange A+B das gleiche ist wie B+A und C*D das gleiche wie D*C wird
> sich die Vision des TO wohl nicht realisieren lassen.....

Und (a+b)+c = a+(b+c) usw. Man dürfte überhaupt keine Gleichungen mehr 
umformen, denn das bedeutet immer Äquivalenz der beiden 
Gleichungsformen. Also garkeine Mathematik mehr.

Gruss Reinhard