Turing-Maschine
englischen Mathematiker Alan Turing
erstes Modell 1936, die in der Lage ist, Rechenoperationen durchzuführen
drei Komponenten:
Speicherband: unendlich lang und enthält undendlich viele Felder hintereinander. In jedem Feld steht genau ein Zeichen (entweder leeres Zeichen oder Zeichen aus Zeichenvorrat der Maschine)
Lese- und Schreibkopf: zum Lesen/Schreiben vom/auf Speicherband. Immer genau ein Zeichen. Nach Aktion bleibt es in Position oder bewegt sich um ein Zeichen nach rechts oder links.
Steuereinheit: merkt sich den aktuellen Zustand der Turing-Maschine
Programm legt fest, was Turing-Maschine macht
drei Operation, mit denn sich sämtliche Probleme lösen lassen, die berechenbar sind:
Lesen von Zeichen
Schreiben von Zeichen
Bewegen des Lese- und Schreibekopfs
-> dadurch lässt sich Church-Turing-These ableiten
kann addieren, subtrahieren, sortieren, tauschen und so weiter
Programme werden aber sehr schnell sehr aufwendig und umfangreich
Church-Turing-These
Alles, was überhaupt berechenbar ist, ist schon mit der Turing-Maschine berechenbar.
-> Alles was nicht mit der Turing-Maschine berechenbar ist, lässt sich gar nicht berechnen.
-> Alles, was eine Turing-Maschine nicht berechnen kann, lässt sich auch nicht mit einem Computer berechnen.
Turing-Test
soll feststellen, ob Computer eine ähnliche Intelligenz wie Menschen haben
dazu “unterhält” sich eine Testperson (ohne es zu wissen) mit einem Computer
wenn sie keinen Unterschied zu einem Menschen feststellen kann, hat der Computer beziehungsweise das Programm den Turing-Test bestanden, was aber bis heute noch nicht gelungen ist
allerdings gibt es einige Programme, dei verblüffend nah rankommen, z.B. ELIZA von Joseph Weizenbaum, aber es ist keineswegs intelligenz, sondern reagiert nur nach festen Mustern auf die Eingaben des Gegenübers
Registermaschine
Modell, was aber einem “echten” Rechner sehr viel näher kommt als die sehr einfache Turing-Maschine
besteht aus
Akkumulator: dient zur Sammlung von Zwischenergebnissen bei Berechnungen
unendlich vielen Speicherzellen, die fortlaufend nummeriert sind
Verarbeitung von Daten in den Speicherzellen erfolgt mit speziellen Befehlen wie zum Beispiel LDA (load to accumulator) für Lade oder STA (store accumulator) für speichere
Berechenbarkeit und Komplexitätstheorie
Automaten und andere Modelle spielen hier eine wichtige Rolle
es geht darum, was und was nicht durch Maschinen berechnet werden kann und wie aufwendig die Berechnung ist
Halteproblem (Beispiel für die Berechenbarkeit): Hier soll berechnet werden, wann ein Programm beendet wird oder nicht. Erster Fall (wenn beendet) ist einfach, aber zweiter Fall lässt sich nicht feststellen, weil ja überhaupt nicht klar ist, wann ein Fehler auftritt
bei der Komplexitätstheorie soll herausgefunden werden, wie komplex und aufwendig eine Lösung durch einen Algorithmus ist. Nicht alle berechenbare Probleme lassen sich mit dem Computer in vertretbarer Zeit lösen (Beispiel: Problem des Handlungsreisenden)
Zuletzt geändertvor 10 Monaten