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.


Molekülsubstanzen?

Heyy wir haben in Chemie jetzt irgendwas...Molekülsubstanzen!!! Und ich checke einfach NICHTS! Ich bin eigentlich ein sehr guter Schüler aber kann mir das irgendwer erklären? Irgendwie ist das, wenn 2 Atome miteinander verbunden werden durch chemische Bindung! Ich kapier gar nichts :(

...zur Frage

Was sind Agile Methoden (Informatik)?

Hallo,

ich schreibe meine Facharbeit in Informatik und müsste den Begriff ''Agile Methode'' irgendwie erklären können undso. Ich habe aber leider keine Ahnung, was das überhaupt ist.

Danke im vorraus. :)

...zur Frage

Theoretische Informatik frage bitte ?

Hallo kann mich jemand diese eine Aufgabe erklären ?

...zur Frage

Wie hat die Epoche der Aufklärung die Religion,die Naturwissenschaften und die Politik geprägt?

---> Wie hat die Epoche der Aufklärung die Religion,die Naturwissenschaften und die Politik geprägt??

Wäre nett,wenn ihr mir helfen könntet :)

Danke schonmal :)

...zur Frage

verstehe das gerund mit präposition nicht!

wir haben grade in der schule das gerund mit präpositionen und ich checke es einfach nicht!! wäre nett wenns mir jemand erklären würde! danköö

...zur Frage

warum soll die gleichgültigkeit das gegenteil von liebe sein...

wo mir menschen, die ich hasse, nicht nicht weniger egal sind? ich mein, ich hasse meinen exfreund und würde nie im leben darauf kommen, mich auf ihn einzulassen weil ich ihn hasse, aber trotzdem isses mir egal, mit wem er was tut oder was er überhaupt tut usw. bzw. seine person ist mir egal, aber ich hasse ihn für alles was er mir angetan hat, bzw. verachte ihn sogar.

könnt ihr mir das erklären? und nein, ich liebe ihn wirklich nicht ;-) also ich finde, dass hass das gegenteil von liebe ist. damals als er mir nur gleichgültig war, wollt ich einfach gar nix von ihm, aber jetzt will ich nicht mehr von ihm und deshalb verwirrt es mich, wahrscheinlich isses ein mix aus hass und gleichgültigkeit. mich verwirrt auch, dass man hass gleich mit liebe und gefühlen für jemanden in verbindung bringt, ich finde das quatsch, man kann jemanden aus ganz verschiedenen gründen hassen und liebt ihn dann hoffentlich auch nicht, das passt einfach nicht. sich zu hassen muss nicht sein, wenn man sich wirklich liebt und deshalb bleibt es für mich das gegenteil von liebe.

ich bin gespannt, was ihr darauf sagt.

danke

...zur Frage

Was möchtest Du wissen?