Alan Turing – den wir bereits vom «Turing-Test» kennen – hatte die Idee eines imaginären Rechnermodells, welche alles berechnen kann, was ein Computer berechnen kann. Die sogenannte Turing-Maschine kann nicht gebaut werden, aber sie dient noch heute als anschauliches Werkzeug der Theoretischen Informatik.
Aufgabe
Arbeit dich durch das unten verlinkte Matheprisma-Kapitel durch und halte Antworten zu den folgenden Fragen schriftlich fest – wenn möglich prägnant und in deinen eigenen Worten:
- Was sind die Bestandteile der Turing-Maschine?
- Wie funktioniert sie?
- Was ist das «Halteproblem»?
- Wie kann man zeigen, dass etwas nicht berechenbar ist?
Lösung
Was sind die Bestandteile der Turing-Maschine?
- Lese- und Schreibkopf
- ein unendlich langer Papierstreifen
- Motor (Lesekopf oder Steifen verschieben)
Wie funktioniert sie?
- Arbeite ein Programm ab
- verwendet den Papierstreifen als Speicher, Ein- und Ausgabe
Was ist das «Halteproblem»?
Es gibt keine Funktion, die für ein beliebiges Programm berechnet, ob dieses je zu einem Ende kommt.
wikipedia: Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt.
Wie kann man zeigen, dass etwas nicht berechenbar ist?
Wir zeigen, dass es mit der Turing-Maschine nicht berechenbar ist.