Turing-Berechenbarkeit

Was ist Berechenbarkeit?

Ein ">Funktion f ist berechenbar, wenn es einen gibt, welcher für jedes Element m der Menge M das ihm zugeordnete Element f(m) in endlich vielen Schritten berechnen kann.

„Effektiv berechenbar” ist eine Funktion dann, wenn ich in jedem Augenblick eindeutig weiß, was als nächstes zu tun ist, und wenn jeder solche Schritt mechanisch mit eindeutig feststellbarem Ergebnis ausführbar ist.[1]

Vermutlich würde man davon ausgehen, dass jede Funktion auch berechenbar ist, dem ist jedoch nicht der Fall. Entgegen dem Allgemeinglauben lässt sich jedoch fast gar nichts berechnen. Der Church- These nach lassen sich allerdings die Funktionen, welche man berechnen kann, verhältnismäßig einfach berechnen: Nämlich mit einer Turingmaschine.

Turingmaschine

Die Turingmaschine ist das Modell einer Maschine, welches Alan Turing 1936 eingeführte, um Algorithmen und Fragen der Berechenbarkeit und Entscheidbarkeit zu untersuchen.
Dabei handelt es sich um eine Zustandsmaschine, welche sich mit einem Lesekopf in zwei Richtungen auf einem Band bewegt und drei einfache Operationen ausführt.

eine Maschine, die ein Band vor- und zurückfährt, Markierungen auf einem Bandabschnitt list, löscht und durch andere ersetzt und die von einem Zustand in den anderen übergeht, wird heute als Turingmaschine bezeichnet. Eine solche Maschine ist vollständig beschrieben, wenn die Beschreibung für jeden Zustand, den sie erreichen, und für jedes Symbol, das sich hinter ihrem Tonkopf befinden kann angibt, welches Symbol auf das Band aufgenommen werden, in welchen Zustand sie übergehen und in welche Richtung das Band bewegt werden soll.[2]

Die Maschine hat immer einen Zustand. Die Kontrolleinheit liest das aktuelle (das sich unter dem Lesekopf befindende) Zeichen auf dem Band aus und referenziert eine Tabelle, in welcher der nächste Zustand der Maschine vermerkt ist. Dieser nächste Zustand ergibt sich also immer aus dem aktuellen Zustand und dem gelesenen Zeichen.

Die Turing-Maschine ist ein ungeheuer einfaches, unglaublich anschauliches und riesig mächtig abstraktes Konzept. In ihm feierte der europäische Geist einen erstaunlichen Höhepunkt an präziser Schlichtheit. Niemand rechnet im Kopf so wie eine Turing-Maschine ihre Zustände aufeinander folgen lässt. und doch beschreibt die Turing-Maschine - vom Ergebnis her betrachtet! - alle unsere Berechnungsprozess![1]

Church-These

Die Church These besagt sinngemäß, dass sich jede berechenbare Funktion auch nach Turing berechnen lässt.

Analog zum Wittgenstein-Zitat „Was sich überhaupt sagen lässt, lässt sich klar sagen, und wovon man nicht sprechen kann, darüber muss man schweigen” ließe sich die Church-These auch folgendermaßen formulieren: Was sich überhaupt berechnen lässt, lässt sich nach Turing berechnen.

Quellen

  1. #nake-algorithmus">Frieder Nake: Funktion Algorithmus Programm und so
  2. #weiz78">[Weiz78, 89 f]