Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Berechenbarkeit

Wir gehen von der Definition für die Berechenbarkeit einer mathematischen Funktion mit Hilfe des Begriffs Algorithmus aus. Diesem liegt ein Berechnungsmodell zugrunde [1]. Da die stärksten Berechnungsmodelle zum Modell der Turingmaschine gleich stark (turing-mächtig) sind, werden für die weiteren Betrachtungen für die Berechenbarkeit die Turingmaschinen herangezogen. [2]

Berechenbarkeit einer mathematischen Funktion

Eine mathematische Funktion ist berechenbar, wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. [1]

Zusammenhang zu den Turingmaschinen

Church-Turing-These

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

Diese These ist nicht beweisbar, da der Begriff "intuitiv berechenbare Funktion" nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. ... Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist. [2]

Definition "berechenbar" [3]

Eine Funktion heißt berechenbar, wenn es eine Turingmaschine gibt, so dass

zu Beginn die Argumente der Funktion auf dem Band stehen,
die Turingmaschine nach endlich vielen Schritten hält
und am Ende der Funktionswert auf dem Band steht.

Aufgaben

Wie wird der Definitionsbereich einer Funktion (siehe Weblink 1) definiert?
Was versteht man unter einem Algorithmus? Welche Eigenschaften hat ein Algorithmus?
Aus der Schule bekannte Beispiele für Algorithmen sind z.B.: euklidischer Algorithmus, Sieb des Eratostenes, Intervallhalbierungsverfahren, Bubblesort, lineare Suche
Geben sie zu jeden dieser Algorithmen an, was diese Algorthmen machen. Beschreiben Sie 2 Beispiele genau (in Stichpunkten).
Erklären Sie im Zusammenhang mit Algorithmen den Begriff "turing-vollständig".
Informieren Sie sich über Alonzo Church.

Weblinks

zurück