Christian Berger schrieb:
> Ein klares Jain!
Ein klares JA
> Eine Turing-Maschine hat ein unendlich langes Band. Sie hat somit
> unendlich viel Speicher. Der Grund warum man Mikrocontroller trotzdem
> noch, streng genommen falsch, als Turing-vollständig ansieht ist, dass
> sie "genügend" Speicher haben.
Ja weil bei der Turingmaschine eben eine Speicherbegrenzung keine Rolle
spielen soll, weil es eben nicht auf den Speicher, sondern auf die
Grundsätzliche Berechenbarkeit eines Problems ankommt.
> Also streng genommen kann es keine realen Turing-Maschinen geben. Wenn
> Du "genügend Speicher" auf ein paar Bits reduzierst wird aber auch jeder
> endliche Automat zur Turing-Maschine.
Nicht nur streng genommen sondern ganz einfach. Es kann keine
Turingmaschine geben. Das war aber auch nicht die Frage. Es geht um
Turing-Vollständig und das bezieht sich allein auf die Berechenbarkeit
und nicht auf den Speicher oder die Rechenzeit oder onst was. Also
spielt es dafür keine Rolle ob nun eine Turingmaschine real existieren
kann oder nicht. Und somit ist die Antwort auf die Ursprüngliche Frage
ein klares JA und sonst gar nichts. Dies würde auch dann gelten wenn ein
Controller überhaupt keinen Speicher hätte, weil es hier einzig auf die
ALU ankommt, d.h. vorallem welche Kontrollstukturen existieren. Und als
Kontrollstruktur reicht bereits ein WHILE oder sogar nur ein GOTO aus
bzw. Befehle welche diese Nachbilden können.
Das wird auch klar wenn man sich die Definition von
Turing-Vollständigkeit ansieht. Dazu muss jedes math. Problem lösbar
sein welches mit einem Algorithmus gelöst werden kann. Dabei spielen in
der realen Welt natürlich IMMER Begrenzungen eine Rolle. Diese
Begrenzungen haben aber keinen Einfluss auf die Tatsache ob eine
logische Einheit Turing-Äquivalent ist oder nicht.
Und btw: Ein DFA/NFA ist nicht Turing-Äquivalent. Eine Turingmaschine
welche sich nur in eine Richtung bewegt UND nur lesen kann, entspricht
einem NFA.
gruß cyblord
