Ist der C64 eigentlich turingfähig und wer kann mir in einfachen Worten erklären, was es mit der Turingfähigkeit auf sich hat?
Hallo Besucher, der Thread wurde 2,1k mal aufgerufen und enthält 5 Antworten
letzter Beitrag von BlondMammuth am
-
-
Vorneweg: Ja, der C64 ist mit seinen Bordsprachen BASIC und ebenso mit Assembler touringvollständig, wobei schon die Architektur der Maschine das bedingt, da eine Touringmaschine sämtliche gegebenen Aufgaben mit drei Mechanismen lösen kann:
1. Lesen aus einem unendlichen Speicher.
2. Schreiben in ebendiesen
3. Wahlfreies Positionieren des SchreiblesekopfesEin Computer kann dann als Touringvollständig angesehen werden wenn man mit ihm eine solche Touringmaschine umsetzen kann und vice versa.
Dies ist mit dem C64 problemfrei möglich. Das Problem des theoretisch benötigten unendlichen Speichers lässt sich durch Massenspeichermedien wie eine Floppy oder ein Tape lösen, zudem ist in der Praxis kein unendlicher Speicher vonnnöten, da eigentlich jedes Problem irgendwann eine finite Lösung erreichen wird (es mag Ausnahmen geben, aber sie dürften in der Zahl sehr gering sein).Es erfolgt dabei keine Aussage wie performant das System sein muss, der C64 wird sehr lange für vieles benötigen, aber grundsätzlich lassen sich mit ihm alle Programme ausführen die denkbar sind.
EDIT:
zur Funktionsweise der Touringmaschine: Die Touringmaschine ist prinzipiell eine State Machine, das heisst sie kann verschiedene Zustände einnehmen. Je nach aktuellem Zustand wird das unter dem Schreiblesekopf befindliche beziehungsweise das gerade bearbeitete Zeichen gewertet um
- eine Eingabe vorzunehmen (lesen)
- Eine ausgabe vorzunehmen (schreiben)
- einen neuen Status einzunehmen (entscheidet die nachfolgenden Operationen)
- die Schreib-Leseposition und/oder Richtung zu ändern (vorwärts rückwärts)
Mit dieser Handvoll Optionen lässt sich - genug Speicher vorausgesetzt- jedweder denkbare Algorithmus umsetzen. Siehe dazu auch Brainfuck - eine Sprache die auf diese Operationen begrenzt ist und nur mit 8 Befehlen, jeweils bestehend aus einem Zeichen, auskommt. -
Gegen so eine alte Turing-Bombe aus dem 2. Weltkrieg ist der C64 quasi ein Großrechner
-
Turing-Fähigkeit - oder auch Turing-Vollständigkeit - heißt konkret: Eine "Maschine", ein Kalkül, ein Rechenmodell, was auch immer, kann im Grunde alle berechenbaren Funktionen berechnen.
Was sind "alle berechenbaren Funktionen"? Das ist ein abstrakter Begriff, für den mehr als so ein Forum nötig wäre, aber es ist vor allem ein mathematischer Begriff. Die berechenbaren Funktionen sind wieder - ein Zirkelschluss - alle, die durch Turing-Maschinen berechnet werden können. Es handelt sich bei den Turing-Maschinen um ein abstraktes Modell für das Rechnen.
Eine Turing-Maschine ist dabei eigentlich ein "Programm", das in diesem Rechen-Modell formuliert ist. Man spricht daher salopp von "der Turing-Maschine", meint damit aber die Gesamtheit aller Turing-Maschinen. Diese berechnen abstrakt gesehen Funktionen, in dem sie eine Eingabe (die eine bestimmte Form hat) einem Programm vorsetzen (das auch eine bestimmte Form hat, und einen Algorithmus abbildet), und dieses Programm hinterlässt eine Ausgabe.
Turing-Maschinen sind nicht die einzigen Berechnungsmodelle, die Algorithmen darstellen können. Es gibt (viele) andere, wie z.B. den Lambda-Kalkül, etc. In Wirklichkeit müsste man also die "Vollständigkeit" relativ zum verwendeten Rechenmodell (also z.B. der Turing-Maschine) definieren. Und da stellt sich z.B. die Frage: Ist Turing-Vollständig z.B. gleich Lambda-Vollständig? Und dieselbe Frage im Bezug auf all die anderen Rechenmodellle? Lassen sich in all denen dieselben Funktionen theoretisch berechnen?
Die Antwort ist zum Glück: Ja. Wenn man ein Rechenmodell so baut, dass es gewisse Dinge kann (die recht leicht aufzuzählen sind: Es muss Schleifen geben, Verzweigungen, und beliebig vielen Speicher, auf den man zugreifen kann), dann kann das Ding immer auch ALLE theoretisch denkbaren berechenbaren Funktionen berechnen, und das ist dann genau dasselbe, was man auch mit Turing-Maschinen zuwege bringt. Man beweist das, in dem man je ein Modell mit dem anderen "simuliert". Das wäre ca. so, als würde man in C einen Pascal-Interpreter schreiben, und dann in Pascal einen C-Interpreter. Dann ist ganz klar, dass jeder Algorithmus, der man in der einen Sprache programmieren kann, grundsätzlich auch in der anderen möglich ist.
Deshalb (und weil Turing einer der Pioniere der theoretischen Informatik war) beschränkt man sich darauf, generell von der "Turing-Vollständigkeit" eines beliebigen Rechenmodells zu sprechen. Auf Deutsch: Wenn man was in dem Modell schafft, dann auch mit einer Turing-Maschine, und umgekehrt.
Jetzt aber zur Praxis, was heißt das für Hardware? Es heißt "ja und nein".
Ja: Einerseits ist jede Programmiersprache (bis auf HTML, SQL, und ein paar anderer solcher Exoten) Turing-vollständig. Kann ich in Basic oder C oder Prolog oder Smalltalk .. ein Programm schreiben, dann kann ich den Algorithmus auch mit einer Turing-Maschine realisieren, und kann ich es mit der Turing-Maschine, gehts auch mit der "realen" Programmiersprache. Klar, ich brauch ja nur ein Programm schreiben, das Turing-Maschinen simuliert, und schon kann ich übersetzen.
Nein: Was nämlich theoretische Modelle IMMER auszeichnet, ist, dass ihnen nie der Speicher und nie die Zeit ausgeht. Die können also theoretisch Trilliarden Jahre mit Phantastilliarden Gigabyte Daten vor sich hin rechnen, ohne jede Beschränkung nach oben. Das gehört zu deren Definition, denn sonst gäbs ja immer berechenbare Funktionen, die man DAMIT doch nicht, aber mit dem größeren Modell sehr wohl berechnen kann. Das wäre widersinnig.
Das ist aber genau das, was reale Computersysteme niemals bieten können. Sie sind also, streng genommen allesamt nicht Turing-vollständig. Aber so genau nimmt man es nicht. Man geht davon aus, dass man den Speicher schon noch irgendwo her bekommt, und grundsätzlich sieht das, was jeder Computer kann, der Turing-Vollständigkeit schon sehr, sehr ähnlich, und tatsächlich: Innerhalb vernünftiger Grenzen ist man Turing-vollständig.
Fazit: Der C64 ist im selben Sinne Turing-vollständig wie jeder programmierbare Computer. Bloß drüber hinaus viel schöner, viel klassischer, und viel langsamer als die meisten anderen.
-
Gegen so eine alte Turing-Bombe aus dem 2. Weltkrieg ist der C64 quasi ein Großrechner
Naja, vor Allem, wenn man bedenkt, daß weder die Turing-Bombe noch Colossus Universalrechner waren. Beides waren ausschließlich Deschiffrierautomaten. Bei der Bombe ist das aber auch nicht richtig. Sie entschlüsselte keine Texte sondern diente dazu qualifizierte Vermutungen über die Anfangsstellung der Enigma zu erhalten, mit denen man weiterarbeiten konnte. Wie das technisch aussah würde hier zu weit führen. Bei Colossus bin ich mir gerade nicht sicher, ob er nicht sogar Klartext ausgab.
-
Naja, vor Allem, wenn man bedenkt, daß weder die Turing-Bombe noch Colossus Universalrechner waren. Beides waren ausschließlich Deschiffrierautomaten. Bei der Bombe ist das aber auch nicht richtig. Sie entschlüsselte keine Texte sondern diente dazu qualifizierte Vermutungen über die Anfangsstellung der Enigma zu erhalten, mit denen man weiterarbeiten konnte. Wie das technisch aussah würde hier zu weit führen. Bei Colossus bin ich mir gerade nicht sicher, ob er nicht sogar Klartext ausgab.
Die Turing-Bombe ist nicht dasselbe wie die Turing-Maschine.
Das Eine, die Turing-Bombe (Colossus beruht zwar auf Turings Vorleistungen, wurde aber nicht von ihm gebaut) ist ein realer Apparat, wie schon von Heiko gut charakterisiert, die Turing für einen praktischen (und enorm kriegswichtigen) Zweck gebaut hat.
Das Andere ist ein davon sehr unterschiedliches theoretisches Konstrukt, das Turing in seiner Eigenschaft als theoretischer Mathematiker in einer sehr berühmten historischen Publikation ersonnen hat, um Gedanken zur Berechenbarkeit auszudrücken.
Die beiden sind Turings bekannteste bahnbrechende Leistungen, gleichermassen von historisch eminenter Bedeutung, aber in völlig verschiedenen Zusammenhängen. Turing wird daher zurecht als einer der wichtigsten Mathematiker des 20. Jahrhunderts in einem Atemzug mit Gödel etc. genannt.