Turing-Maschinen und Registermaschinen

• 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

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.

• 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

• 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

• 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)