Turingmaschine / Churchsche These?

5 Antworten

Unter dem Konzept der Turingmaschine versteht man eine extrem einfache (nur theoretisch Sinn machende) Rechnerarchitektur. Alan Turing hat sie ersonnen mit den Ziel, zeigen zu können: Berechenbar mit Hilfe eines Computers (einem Computer mit sog. von-Neumann-Architektur) sind genau die Dinge, die mit Hilfe einer Turingmaschine berechenbar sind.

Alle Computer, die man bisher kennt, sind Computer mit von-Neumann-Architektur.

In Konkurrenz zu Turing haben auch andere Informatiker - z.B. Church und Rosser - eine Charakterisierung der per von-Neumann-Computer möglichen Berechnungen zu finden. Ihre Lösungen waren unübersichtlicher als die von Turing, haben sich aber schließlich als dazu äquivalent herausgestellt.

Deswegen gilt bis heute: Durch algorithmische Berechnung lösbar (d.h. mit Hilfe eines nach dem von-Neumann-Prinzip gebauten Computers lösbar) sind genau die Probleme, zu denen es eine Turingmaschine gibt, die - angesetzt auf das Problem - nach endlicher Zeit anhält. 

Dass Turingmaschinen nur theoretisch Sinn machen, liegt daran, dass das Band, mit dem sie arbeiten (sprich: der Speicher, auf den sie schreiben und von dem sie lesen) als unbegrenzt groß angenommen werden muss. Er entspricht dem virtuellen Adressraum eines gewöhnlichen Computers - mit dem kleinen Unterschied allerdings, dass letzterer nur endlich groß sein kann.

Die These von Church:

Eine Funktion ist berechenbar im intuitiven Sinne, genau dann, wenn sie Turing-berechenbar ist.

Diese These ist nicht beweisbar, da es für den Begriff intuitiver Berechenbarkeit keine formale Definition gibt.

0

Die Turing-Maschine ist ein theoretisches Konstrukt, mit dem die Berechenbarkeit und Endlichkeit von Algorithmen untersucht werden kann.

Mit der Church-Turing-These gehst du schon ein gutes Stück in die theoretische Informatik. Die These lautet

Die Klasse der turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.

Ohne tiefere Beschäftigung mit dem Thema wird dir diese Aussage aber nicht viel nützen.

Die Turingmaschine stelt einen Algorithmus dar und kann ihn Schritt für Schritt berechnen.

Die Churchsche These besagt im Grunde, dass es mehr definierbare als berechenbare Funktionen gibt. Sprich: nicht alle Funktionen können von Computern gelöst werden.


Was möchtest Du wissen?