Frage von Tegaru, 34

Turingmaschine / Churchsche These?

Theoretische Informatik: Kann mir jemand mal erklären, was die Turingmaschine genau macht bzw. bringt? Außerdem würde ich gerne wissen, was die Church-Turing These besagt. Bitte ganz einfach für Dumme erklären, damit ich überhaupt irgendeinen Anhaltspunkt habe, weil ich einfach überhaupt nichts checke.

Dankeschön.

Antwort
von NeoExacun, 24

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.

Antwort
von grtgrt, 14

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.

Kommentar von grtgrt ,

Ein besonders interessantes Beispiel dafür, wie man mit Hilfe des Konzepts der Turingmaschine zu neuer Erkenntnis kommt, findet sich diskutiert in Notiz http://greiterweb.de/zfo/Intelligenz-echte-vs-kuenstliche.htm#msgnr0-205 .

Kommentar von grtgrt ,

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.

Antwort
von Herb3472, 19

Vielleicht hilft Dir das hier weiter:

https://www.youtube.com/results?search_query=church+turing+these

Antwort
von qugart, 20

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.


Keine passende Antwort gefunden?

Fragen Sie die Community