Post on 06-Apr-2015
transcript
Grenzen der Berechenbarkeit
Klaus Becker
2007
2 Algorithmen
Zielsetzung: Grenzen der Berechenbarkeit kennen Methoden zum Nachweis der Grenzen verstehen
„Die mathematische Präzisierung des Algorithmusbegriffs und die
Erkenntnis der Grenzen der Algorithmisierbarkeit gehören zu
den größten intellektuellen Leistungen des zwanzigsten
Jahrhunderts.“ (Kirchler)
3 Teil 1
Das Halteproblem
4 Frustrierende Erlebnisse
Jeder hat schon einmal die Erfahrung gemacht, dass der Rechner aus irgendwelchen Gründen nicht mehr reagiert. Soll man noch warten, oder ...
Mein Rechner hat sich schon wieder aufgehängt!
5 Aufgabe
Testen Sie die folgenden Primzahlprogramme (siehe "primzahlen.py"). Geben Sie jeweils die Startzahl ... (sollte groß gewählt werden) vor.
Eingabe: Startzahl nAusgabe: nächst größere Primzahl
Eingabe: Startzahl nAusgabe: nächst größeres Primzahlzwillingspaar
Eingabe: Startzahl nAusgabe: nächste Primzahl, die nicht neben einer 6er-Zahl liegt
Programm 1 - Primzahlsuche
Programm 2 - Primzahlzwillinge
Programm 3 – Primzahl nicht neben 6er-Zahl
6 Beobachtung
Bei groß gewählter Startzahl halten die Programme vorerst nicht.
Eingabe: Startzahl nAusgabe: nächst größere Primzahl
Eingabe: Startzahl nAusgabe: nächst größeres Primzahlzwillingspaar
Eingabe: Startzahl nAusgabe: nächste Primzahl, die nicht neben einer 6er-Zahl liegt
Programm 1 - Primzahlsuche
Programm 2 - Primzahlzwillinge
Programm 3 – Primzahl nicht neben 6er-Zahl
7 Lohnt es sich zu warten?
Eingabe: Startzahl nAusgabe: nächst größere PrimzahlBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 1 - Primzahlsuche
Eingabe: Startzahl nAusgabe: nächst größeres PrimzahlzwillingspaarBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 2 - Primzahlzwillinge
Eingabe: Startzahl nAusgabe: nächste Primzahl, die nicht neben einer 6er-Zahl liegtBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 3 – Primzahl nicht neben 6er-Zahl
Eingabe: Startzahl nAusgabe: nächst größere PrimzahlBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 1 - Primzahlsuche
Hält immer (kann aber sehr lange dauern).
Eingabe: Startzahl nAusgabe: nächst größeres PrimzahlzwillingspaarBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 2 - Primzahlzwillinge
Hält für kleine n. Ob dies für alle n gilt, ist nicht bekannt.
Eingabe: Startzahl nAusgabe: nächste Primzahl, die nicht neben einer 6er-Zahl liegtBei Eingabe von großen n hält das Programm (vorerst?) nicht.
Programm 3 – Primzahl nicht neben 6er-Zahl
Hält außer für 1, 2 und 3 nie.
8
Ein Analyseprogramm für Ungeduldige
Ziel ist es, ein Programm zu entwickeln, mit dessen Hilfe man Endlosschleifen bei beliebigen Programmen feststellen kann. Wir betrachten hier zunächst die Analyse von Python-Programmen.
falls das Python-Programm bei Eingabe der Daten hält,sonst
True
False
Python-Programm +
Eingabedaten
9
Textanalyse bei Python-Programmen
Wir vereinfachen das Problem: Getestet werden soll zunächst, ob ein Python-Programm eine while-Anweisung enthält.
falls das Python-Programm eine while-Anweisung enthält,sonst:
analyseWhile True
False
Python-Programm
10 Aufgabe
Testen Sie das folgende Analyseprogramm (siehe "analyseWhile.py"). Lassen Sie es verschiedene Python-Programme / beliebige Texte analysieren. Testen Sie auch den Fall, dass das Programm seinen eigenen Quelltext analysiert.
def analyseWhile ( dateiname ) : try : datei = file ( dateiname ) quelltext = datei.read ( ) datei.close ( ) print quelltext except : return 'FehlerBeimLaden‚ liste = quelltext.split ( ) print liste gefunden = False for i in range ( 0 , len ( liste ) - 1 ) : if liste [ i ] == 'while' : gefunden = True return gefunden
ggt1.py
>>> analyseWhile('ggt1.py')
def ggt ( x , y ) : while y > 0 : h = x % y x = y y = h return x
11 Aufgabe
Modifizieren Sie das Analyseprogramm so, dass es rekursive Python-Programme erkennen kann. Gehen Sie vereinfachend davon aus, dass die zu analysierenden Programme in einer Token-basierten Form vorliegen (der Quelltext ist hier so gestaltet, dass die einzelnen Bausteine / Token durch Leerzeichen getrennt sind wie im Beispiel unten).
def ggt ( x , y ) : if x == y : return x else : if x > y : return ggt ( x - y , y ) else : return ggt ( x , y - x )
nicht rekursiv
def ggt ( x , y ) : while y > 0 : h = x % y x = y y = h return x
rekursiv
12 Aufgabe
Ein Analyseprogramm soll testen, ob eine der in der Abbruchbedingung einer while-Anweisung vorkommenden Variablen innerhalb des Restprogramms einen Wert zugewiesen erhält.
Beurteilen Sie auch den eingeschlagenen Weg, das Terminationsverhalten eines Programms anhand syntaktischer Eigenschaften des Quelltextes abzulesen.
def ggt ( x , y ) : while y > 0 : h = x % y x = y y = h return x
kritische Variable
13 Selbsthaltende Programme
Ein (Python-)Programm heißt selbsthaltend, wenn es bei Eingabe seines eigenen Quelltextes hält.
Gibt es ein Programm "analyseSelbsthaltend", das entscheiden kann, ob ein Python-Programm selbsthaltend ist?
falls,das Python-Programm bei Eingabe des eigenen Quelltextes hält, sonst:
analyseSelbsthaltend
True
False
Python-Programm
14 Aufgabe
Wie würde sich dieses "seltsame" Programm bei der Analyse von Quelltexten / seines eigenen Quelltextes verhalten? Gehen Sie von der Annahme aus, dass der kommentierte Teil des Programms durch geeignete Anweisungen realisiert ist.
def seltsam(dateiname):
# wenn das (unter dem Dateinamen abgespeicherte Programm) # selbsthaltend ist: # dann wird der Wert der Variablen selbsthaltend # auf True gesetzt, # sonst # wird der Wert auf False gesetzt.
if selbsthaltend: while True: selbsthaltend = selbsthaltend return selbsthaltend
15 Ein seltsames Programm
Das Programm 'seltsam.py' kehrt den Spieß um:
falls,das Python-Programm bei Eingabe des eigenen Quelltextes hält, sonst:
seltsam hält nicht
hält
Python-Programm
16 Ein seltsames Programm
Wenn das Programm 'seltsam.py' sich selbst analysiert, dann ergibt sich eine widersprüchliche Situation: 'seltsam.py' hält nicht bei Eingabe des eigenen Quelltextes genau dann, wenn es bei Eingabe des eigenen Quelltextes hält.
falls,das 'seltsam.py' bei Eingabe des eigenen Quelltextes hält, sonst:
seltsam hält nicht
hält
'seltsam.py'
17 Spezielles Halteproblem
Problem:Gibt es ein Programm "analyseSelbsthaltend", das entscheiden kann, ob ein Python-Programm selbsthaltend ist?
Annahme:Es gibt ein solches Programm .
Konstruktion:Dann gibt es ein modifiziertes Programm 'seltsam.py', das sich wie folgt verhält:
seltsam hält nicht
hält
Python-Programm
falls,das Python-Programm bei Eingabe des eigenen Quelltextes hält, sonst:
18 Spezielles Halteproblem
Argumentation:Wenn das Programm 'seltsam.py' sich selbst analysiert, dann ergibt sich eine widersprüchliche Situation:
falls,das 'seltsam.py' bei Eingabe des eigenen Quelltextes hält, sonst:
seltsam hält nicht
hält
'seltsam.py'
Folgerung:Die Annahme, dass es ein Programm "analyseSelbsthaltend" gibt, muss falsch sein.
19 Entscheidbarkeit
falls,das Wort zur Sprache gehört, sonst:
Programm
Wort
Beachte:Das Programm muss für jede Eingabe halten und eine der beiden Ausgaben "True" bzw. "False" erzeugen.
Definition: Eine Sprache über einem Alphabet heißt (Python-) entscheidbar, wenn es ein (Python-) Programm gibt, das für jedes Wort über dem Alphabet feststellt, ob es zur Sprache gehört oder nicht.
True
False
20 Entscheidbarkeit
Fazit:Das spezielle Halteproblem (Hält ein Programm, wenn es seinen eigenen Quelltext bearbeitet?) ist nicht (Python-) entscheidbar.
Satz: Die Sprache der Python-Quelltexte, die zu einem Programm gehören, das bei Eingabe des eigenen Quelltextes hält, ist nicht (Python-) entscheidbar.
falls,das Python-Programm bei Eingabe des eigenen Quelltextes hält, sonst:
True
False
Python-Programm
21 Weitere Ergebnisse
Termination ist nicht entscheidbar:Es gibt kein (Python-) Programm zur Entscheidung von Termination, d. h. ob ein beliebig vorgegebenes Programm bei Eingabe beliebiger Daten hält.
Korrektheit ist nicht entscheidbar:Es gibt kein (Python-) Programm zur Entscheidung von Korrektheit, d. h. ob ein beliebig vorgegebenes Programm bei Eingabe beliebiger Daten eine im Vorfeld festgelegte Eigenschaft hat.
22 Beurteilung der Ergebnisse
Irren ist menschlich. Solange Menschen Programme schreiben, werden diese mit Fehlern behaftet sein. (Sneed)
Eine unzuverlässige Programmiersprache, aus der unzuverlässige Programme hervorgehen, bedeutet eine größere Gefahr für die Gesellschaft als unsichere Automobile, giftige Schädlingsbekäpfungsmittel oder undichte Reaktoren in Kernkraftwerken. (Hoare)
23 Teil 2
Berechenbarkeit als Problem
24 Vorsicht: Verallgemeinerungen
Etwas unvorsichtige Äußerung eines Herausgebers einer Software-Zeitschrift, der seine Erfahrungen über die Entwicklungen in der Informatik beschreibt
(zitiert nach D. Harel: Das Affenpuzzle und weitere bad news aus der Computerwelt)
„Geben Sie einem Computer die richtige Software, und er wird tun, was immer Sie wünschen. Die Maschine selbst mag Grenzen haben, doch für die Möglichkeiten von Software gibt es keine Grenzen.“
Das (spezielle) Halteproblem ist nicht Python-entscheidbar.D.h.: Es gibt keinen Algorithmus, mit dem man das (spezielle) Halteproblem lösen kann.
Etwas schnelle Verallgemeinerung von Programmen in einer speziellen Programmiersprache zu beliebigen Algorithmen
In beiden Fällen werden Aussagen über das algorithmisch Machbare getroffen. Dies ist insofern problematisch, da hier Aussagen über alle denkbaren Algorithmen gemacht werden.
25 (Un-)Möglichkeitsnachweise
Möglichkeitsnachweis:Man entwickelt einen geeigneten Algorithmus.
Da 1*1 = 1, ist die Zahl schon gefunden.
Es gibt eine Zahl, deren Quadrat 1 ergibt.
Es gibt keine Zahl, deren Quadrat -1 ergibt.
Unter "Zahlen" verstehen wir hier reelle Zahlen.Aus den Festlegungen über die Multiplikation reeller Zahlen folgt, dass für jede reelle Zahl x gilt: x*x ≥ 0.Also gibt es keine reelle Zahl, deren Quadrat -1 ergibt.
Es gibt einen Algorithmus, der ... leistet.
Es gibt keinen Algorithmus, der ... leistet.
Unmöglichkeitsnachweis:Man muss zeigen, dass es keinen Algorithmus gibt, der das gestellte Problem löst. Dies erfordert letztlich, dass man den Algorithmusbegriff präzisiert.
26 Was ist ein Algorithmus?
Möglichkeitsnachweis:Man entwickelt einen geeigneten Algorithmus
Es gibt einen Algorithmus, der ... leistet.
Es gibt keinen Algorithmus, der ... leistet.
Unmöglichkeitsnachweis:Man muss zeigen, dass es keinen Algorithmus gibt, der das gestellte Problem löst. Dies erfordert letztlich, dass man den Algorithmusbegriff präzisiert.
Zielsetzung:Um Nachweise über alle möglichen Algorithmen führen zu können, benötigt man eine Klärung des Algorithmusbegriffs. Ziel der folgenden Betrachtungen ist es daher, diesen Begriff möglichst präzise zu beschreiben.
27 Aufgabe
Welche der folgenden Verfahren würden Sie als Algorithmus bezeichnen?
Eingabe: a/b und c/dSei g der ggT von b und d.Sei b = m*g und d = n*g.Sei x = (n*a + m*b).Sei y = m*n*g.Ausgabe: x/y
GGT - Version 2
{x = a; y = b; a,b natürliche Zahlen größer 0}
SOLANGE y > 0
x > yja nein
x := x - y y := y - x
{x = ggT(a,b)}
Eingabe: Polynomgleichung p mit ganzzahligen Koeffizienten, in der verschiedene Variablen mit verschiedenen Exponenten vorkommen können (wie z. B. x3 + 5x2y2z – xz + 37 = 0) Wenn p ganzzahlige Lösungen hat, dann bestimme ein Lösungstupel t. Ausgabe: t
"Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst."
def ggt(x, y): while y > 0: h = x % y x = y y = h return x
28 Aufgabe
Ein Algorithmus ist eine endliche Folge von Instruktionen, die alle eindeutig interpretierbar und mit endlichem Aufwand in endlicher Zeit ausführbar sind. Algorithmen enthalten Instruktionen zur Formulierung von (beliebig vielen) Wiederholungen anderer Instruktionen. Unabhängig von den Werten der Eingangsgrößen endet ein Algorithmus stets nach endlich vielen Instruktionsschritten. Ein Programm ist dann ein Algorithmus, wenn für alle möglichen Eingabewerte sichergestellt ist, dass keine Instruktion unendlich oft wiederholt wird. (Knuth)
Vergleichen Sie die Begriffsdefinitionen. Welches sind die definierenden Eigenschaften des Algorithmusbegriffs? Warum ist es so schwierig, den Begriff "Algorithmus" präzise zu klären?
Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefasste, endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-) Schritte. (Bauer, Goos)
Ein Algorithmus ist ein endliches schrittweises Verfahren zur Berechnung gesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl ausführbarer eindeutiger Operationen und einer Angabe über den nächsten Schritt besteht. (Rechenberg)
siehe: http://www.swe.uni-linz.ac.at/teaching/lva/ss02/algo1_vorlesung/hinweise.html
29 Intuitiver Algorithmusbegriff
nach: Gasper, Leiß, Spengler, Stimm: Technische und theoretische Informatik. bsv Merkert: http://www.hsg-kl.de/faecher/inf/algorithmus/definition/index.php
"Definition":Ein Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie auch von einer Maschine abgearbeitet werden kann.Ein Algorithmus ist eindeutig,d. h.: die einzelnen Schritte und ihre Abfolge sind unmissverständlich beschrieben ausführbar,d. h.: der "Prozessor" muss die Einzelschritte abarbeiten können endlich,d. h.: seine Beschreibung besteht aus einem Text endlicher Länge allgemein,d. h.: es wird nicht nur ein Problem, sondern eine ganze Klasse von Problemen gelöst
30 Intuitiver Algorithmusbegriff
"Definition":Ein Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie auch von einer Maschine abgearbeitet werden kann.Ein Algorithmus ist eindeutig,d. h.: die einzelnen Schritte und ihre Abfolge sind unmissverständlich beschrieben ausführbar,d. h.: der "Prozessor" muss die Einzelschritte abarbeiten können endlich,d. h.: seine Beschreibung besteht aus einem Text endlicher Länge allgemein,d. h.: es wird nicht nur ein Problem, sondern eine ganze Klasse von Problemen gelöst
nicht präzise
Die oben aufgeführte Begriffsklärung ist keine präzise Definition im mathematischen Sinne. Ziel ist es, die informelle Begriffsklärung durch eine präzise Definition im mathematischen Sinne zu ersetzen.
31 Berechnungsmodelle
Ansatz:Die Festlegung des Algorithmusbegriffs bezieht sich auf ein streng definiertes Berechnungsmodell, das genau vorschreibt, was unter „ausführbar“ zu verstehen ist.
Ansatz:Die Festlegung des Algorithmusbegriffs bezieht sich auf ein streng definiertes Berechnungsmodell, das genau vorschreibt, was unter „ausführbar“ zu verstehen ist.
Maschinenorientierter Ansatz: Präzisierung des Prozessors
Zuordnungsorientierter Ansatz: Präzisierung der E/A-Zuordnungen
Anweisungsorientierter Ansatz: Präzisierung der zulässigen Anweisungen
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
32
Anforderungen an Berechnungsmodelle
Anforderungen an ein Berechnungsmodell:Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen es kann Rechenoperationen ausführen es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Anforderungen an ein Berechnungsmodell:Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen es kann Rechenoperationen ausführen es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
33 Teil 3
Turingmaschinen und Marienkäfer
34 Ein erstes Berechnungsmodell
http://www.alanturing.net/
Alan Mathison Turing FRS OBE (born 23 June 1912 at 2 Warrington Crescent, London W9, died 7 June 1954 at his home in Wilmslow, Cheshire) contributed to mathematics, cryptanalysis, logic, philosophy, biology, and formatively to computer science, cognitive science, Artificial Intelligence and Artificial Life.
Educated at Sherborne School in Dorset, Turing went up to King's College, Cambridge in October 1931 to read Mathematics. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. ...
Alan Mathison Turing FRS OBE (born 23 June 1912 at 2 Warrington Crescent, London W9, died 7 June 1954 at his home in Wilmslow, Cheshire) contributed to mathematics, cryptanalysis, logic, philosophy, biology, and formatively to computer science, cognitive science, Artificial Intelligence and Artificial Life.
Educated at Sherborne School in Dorset, Turing went up to King's College, Cambridge in October 1931 to read Mathematics. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. ...
Ein erstes Berechnungsmodell wurde 1936 von A. Turing entwickelt - die sog. Turingmaschine.
35 Turings Idee ...
„Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. [...]“
„The behaviour of the computer at any moment is determined by the symbols which he is observing and his “state of mind” at that moment. [...]“
„Let us imagine the operations performed by the computer to be split up into “simple operations” which are so elementary that it is not easy to imagine them further divided. [...]“
aus: Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society
3 6 2 7
7 2
2 5 2
9 7 2
36
... umgesetzt mit einem Marienkäfer
Kara ist ein Marienkäfer. Kara lebt in einer Welt mit unbewegliche Baumstümpfen, Pilzen, die Kara verschieben kann und Kleeblättern, die Kara legen und aufnehmen kann.
37 Kara´s Sicht der Welt
Kara hat Sensoren, mit denen er/sie die Umwelt wahrnimmt:
stehe ich vor einem Baumstumpf?
ist links von mir ein Baumstumpf?
ist rechts von mir ein Baumstumpf?
stehe ich vor einem Pilz?
stehe ich auf einem Kleeblatt?
Kara versteht einige Befehle,die er/sie folgsam ausführt:
mache einen Schrittvorwärts!
drehe um 90° nach links!
drehe um 90° nach rechts!
lege ein Kleeblatt hin!
nimm ein Kleeblatt auf!
38 Kara soll ein Problem lösen
Kara soll bis zum nächsten Baumstumpf, einmal um ihn herum und anschließend zurück zum Ausgangspunkt laufen.AZ:
...
ZZ:
39 Steuerung von Kara
Bedingung: Aktionen:Akt. Zustand: Neuer Zustand:
markieren hin
hin nein hin
hin ja zurück...
zurück nein zurück
zurück ja stop
mark. hin stop/ Blatt hinlegen
Vor Baum? nein / vorwärts
Vor Baum? ja / links; ...
zurück
Auf Blatt? nein / vorwärts
Auf Blatt? ja / links; links
40 Kara lernt rechnen
Kara soll Rechenaufgaben wie mit einem Abakus durchführen. Zum Rechnen benutzt Kara Kleeblätter. Eine Additionsaufgabe sieht wie folgt aus:
AZ: Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ: Kara hat eine Blattreihen der Länge m+n erzeugt.
41 Steuerung von Kara
Bedingung: Aktionen:Akt. Zustand: Neuer Zustand:
SchrittVor BlattAufhenen
BlattAufheben nein stop
BlattAufheben ja LueckeSuchen
LueckeSuchen nein LueckeSuchen
LueckeSuchen ja ZurueckLaufen
Schritt-Vor
stop/ vorwärts
Auf Blatt? ja / aufheben;vorwärts
Auf Blatt? ja / hinlegen; links; links
Auf Blatt? nein / vorwärts
Blatt-Aufhebe
n
Luecke-Suchen
Zurueck-Laufen
Auf Blatt? nein /
Auf Blatt? nein / links; links
Auf Blatt? ja / vorwärts
ZurueckLaufen nein ZurueckLaufen
ZurueckLaufen ja stop
42 Darstellung im Programm
AZ: Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ: Kara hat eine Blattreihen der Länge m+n erzeugt.
43 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zur Lösung des Problems:AZ: Kara sieht in Blickrichtung eine beliebig lange
Baumstumpfreihe.
ZZ: Kara umläuft die Baumstümpfe und bleibt stehen.
44 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zur Lösung des Problems:AZ: Kara sieht in
Blickrichtung eine beliebig lange vertikale Baumstumpfreihe.
ZZ: Kara umläuft die Baumstumpfreihe und bleibt in der Verlängerung seines Wegs stehen.
45 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zum Verdoppeln:
AZ: Kara steht vor einer beliebig langen Blattreihe der Länge n (die auch 0 sein kann).
ZZ: Kara hat eine Blattreihe der Länge 2n erzeugt.
46 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zur Subtraktion:
AZ: Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ: Falls mn ist, hat Kara eine Blattreihe der Länge m-n erzeugt.
47 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zur Subtraktion:
AZ: Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ: Falls m<n ist, kommt Kara nicht mehr klar und dreht sich ständig im Kreis herum.
48 Aufgabe
Entwickeln Sie einen "Kara-Algorithmus" zur Multiplikation:AZ: Kara steht vor zwei beliebig langen, durch eine leere
Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ: Kara hat eine Blattreihe der Länge mn erzeugt.
49 Turingmaschine
I I II
q0
Ein-/Ausgabeband
Schreib-/Lesekopf
Zustandsbasierte Verarbeitungseinh
eit
Die Turingmaschine besteht aus - einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden. (Man darf sich das unendliche lange Band auch als ein endliches vorstellen, es muss jedoch lang genug sein, um die aktuelle Berechnung ungehindert ausführen zu können, d. h. der Lese- und Schreibkopf darf nicht an das Ende stoßen.) - einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann. Eine Turingmaschine modifiziert die Eingabe auf dem Band nach einem gegebenen Programm. Ist die Berechnung beendet, so befindet sich das Ergebnis auf dem Band. Es wird somit jedem Eingabewert ein Ausgabewert zugeordnet. siehe: http://de.wikipedia.org/wiki/Turingmaschine
I
50 Variationen der Turingmaschine
AZ: I I II
z0
z0
I ;II;RR
; ;LSz1
; ;RS
I ;I ;LS
z2
; ;SSz3
I ;II;RR2-Band-Turingmaschine
2-dimensionale Turingmaschine
51 Arbeitsweise der Turingmaschine
Turingmaschine (dargestellt mit einem Zustandsgraphen):Turingmaschine (dargestellt mit einem Zustandsgraphen):
AZ:
Berechnungsproblem: Addition von „Strichzahlen“Berechnungsproblem: Addition von „Strichzahlen“
I II II
ZZ: I I I II
z0
S
z0
I; I; R
; I; Rz1
; ; L
I; I; R
z2
I; ; Lz3
; ; R
I; I; L
z4
I; I; S
Geschriebenes Zeichen
Aktion
Gelesenes Zeichen
52 Arbeitsweise der Turingmaschine
Turingmaschine (dargestellt mit einem Zustandsgraphen):Turingmaschine (dargestellt mit einem Zustandsgraphen):
Turingmaschine (dargestellt mit einer Zustandstafel):Turingmaschine (dargestellt mit einer Zustandstafel):
z0
I; I; R
; I; Rz1
; ; L
I; I; R
z2
I; ; Lz3
; ; R
I; I; L
z4
I; I; S
Geschriebenes Zeichen
Aktion
Gelesenes Zeichen
alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand
Z0 I I R Z0Z0 ' ' I R Z1
Z1 I I R Z1Z1 ' ' ' ' L Z2
...
53 Aufgabe
Zeigen Sie, dass die folgenden Rechenoperationen von einer Turingmaschine ausgeführt werden können:
Verdopplung einer natürlichen Zahl (dargestellt als Strichzahl) Addition von zwei natürlichen ZahlenSubtraktion von zwei natürlichen ZahlenMultiplikation von zwei natürlichen Zahlen...
Übertragen Sie für eines der Berechnungsprobleme das bereits entwickelte Kara-Programm in ein entsprechendes Turingmaschinen-Programm.
Zeigen Sie, dass die folgenden Rechenoperationen von einer Turingmaschine ausgeführt werden können:
Verdopplung einer natürlichen Zahl (dargestellt als Strichzahl) Addition von zwei natürlichen ZahlenSubtraktion von zwei natürlichen ZahlenMultiplikation von zwei natürlichen Zahlen...
Übertragen Sie für eines der Berechnungsprobleme das bereits entwickelte Kara-Programm in ein entsprechendes Turingmaschinen-Programm.
54 Aufgabe
Testen Sie auch den Turingmaschinen-Simulator von MathePrisma. Schauen Sie sich die Arbeitsweise von verschiedenen Turingmaschinen an (u. a. zum Sortieren).
Testen Sie auch den Turingmaschinen-Simulator von MathePrisma. Schauen Sie sich die Arbeitsweise von verschiedenen Turingmaschinen an (u. a. zum Sortieren).
55 Teil 4
Turingmaschine als universelles Berechnungsmodell
56
Anforderungen an Berechnungsmodelle
Anforderungen an ein Berechnungsmodell:Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen es kann Rechenoperationen ausführen es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Anforderungen an ein Berechnungsmodell:Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen es kann Rechenoperationen ausführen es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
57
Präzisierung des Berechnungsmodells
Definition: Eine Turingmaschine ist ein Tupel T = (X, B, b, Z, z0, ) bestehend aus - einer endlichen, nichtleeren Menge X von Eingabezeichen, - einer Menge B mit X B von Bandzeichen,- einem speziellen Bandzeichen b B \ X („Blank“), - einer endlichen, nichtleeren Menge Z von Zuständen,- einem Anfangszustand z0Z,- einer Überführungsfunktion : Z x B B x {L, R, S} x Z
alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand
Z0 I I R Z0Z0 ' ' I R Z1
Z1 I I R Z1Z1 ' ' ' ' L Z2
...
58 Berechenbarkeit
Definition: Eine Funktion f: N N heißt Turingmaschinen-berechenbar, gdw gilt: Es gibt eine Turingmaschine T mit der folgenden Eigenschaft:
AZ: Auf dem Band befindet sich n dargestellt als Strichzahl.
ZZ: Fall 1: f(n) ist definiert:T hält und hat f(n) dargestellt als Strichzahl erzeugt.
Fall 2: f(n) ist undefiniert (kurz: f(n) = ):T hält nicht.
II
z0
II II
Analog für f: N x N x ... x N N
59 Ergebnisse
Satz: Die folgenden Funktionen sind Turing-berechenbar:f(n) = 2nf(m, n) = m + nf(m, n) = IF(mn, m-n, )f(m, n) = mn...
60 Zwischenbilanz
Zielsetzung:Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie auch im oben beschriebenen Sinn programmierbar ist.
Zielsetzung:Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie auch im oben beschriebenen Sinn programmierbar ist.
Was leistet das Berechnungsmodell "Turingmaschine"? Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. Sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Was leistet das Berechnungsmodell "Turingmaschine"? Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. Sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
61 Universelle Berechnungsmodelle
Daten
Programm
Daten
Computer sind programmierbar!Ein universelles Berechnungsmodell sollte in der Lage sein, nicht nur Eingabedaten in einer ganz bestimmten Weise zu verarbeiten, sondern Eingabedaten nach einem beliebigen ebenfalls einzugebenden Verarbeitungsprogramm zu verarbeiten.
Computer alsprogrammierbar
esSystem
62 Universelle Turingmaschine
Eine universelle Turingmaschine besitzt die Fähigkeit, beliebige andere Turingmaschinen zu simulieren. Als Eingabe erhält sie die Beschreibung der zu simulierenden Turingmaschine und der Daten auf dem Eingabeband für diese Turingmaschine. Eine universelle Turingmaschine ist somit ein Turingmaschinen-Interpreter.
universelle Turingmaschine
1 0 1 1 0 1 1 1 #
z1
1;0;R0;1;R
#;#;Sz0
0 1 0 0 1 0 0 0 #
Eingabeband
Eingabeband
Turingmaschine zum Invertieren einer 0-1-Zeichenkette
63 Simulation mit Turing-Kara
Kodierung der TM
Ein-/Ausgabeband
Vgl.: Turingkara – Aufgaben: Die universelle Turingmaschine
Aktueller Zustand
z1
1;0;R0;1;R
#;#;Sz0
1 0 1 0 1 0 1 0 1 #
64 Aufgabe
Testen Sie die universelle Turingmaschine der Turing-Kara-Umgebung. Versuchen Sie insbesondere zu verstehen, wie diese universelle Turingmaschine arbeitet. Verändern Sie auch die Bandbelegung zu Beginn der Simulation. Versuchen Sie auch, die Arbeitsweise einer weiteren Turingmaschine (z. B. zum Verdoppeln von Strichzahlen) zu simulieren.
Testen Sie die universelle Turingmaschine der Turing-Kara-Umgebung. Versuchen Sie insbesondere zu verstehen, wie diese universelle Turingmaschine arbeitet. Verändern Sie auch die Bandbelegung zu Beginn der Simulation. Versuchen Sie auch, die Arbeitsweise einer weiteren Turingmaschine (z. B. zum Verdoppeln von Strichzahlen) zu simulieren.
65 Simulation mit dem MPG-Simulator
Vgl.: U. Mayr: Theoretische Informatik am PC, S. 18 ff. Programm: Bsp-206.tm
0 R I1 * I * ...
I
1 0 #
10#
z0
1;0;R0;1;R
#;#;Sz1
Ein-/Ausgabe-BandAktueller Zustand
Kodierung der Turing-Tafel
Kodierung: alter Zustand als Strichzahl+1; Leerzeichen; altes Zeichen; neues Zeichen; Bewegung; neuer Zustand als Strichzahl+1
66 Aufgabe
Testen Sie die universelle Turingmaschine der MPG-Simulationsumgebung. Versuchen Sie insbesondere zu verstehen, wie diese universelle Turingmaschine arbeitet. Verändern Sie auch die Bandbelegung zu Beginn der Simulation. Versuchen Sie auch, die Arbeitsweise einer weiteren Turingmaschine (z. B. zum Verdoppeln von Strichzahlen) zu simulieren.
Testen Sie die universelle Turingmaschine der MPG-Simulationsumgebung. Versuchen Sie insbesondere zu verstehen, wie diese universelle Turingmaschine arbeitet. Verändern Sie auch die Bandbelegung zu Beginn der Simulation. Versuchen Sie auch, die Arbeitsweise einer weiteren Turingmaschine (z. B. zum Verdoppeln von Strichzahlen) zu simulieren.
67 Universelle Turingmaschine
Band
Ein-Band-TM
Band
Die universelle Turingmaschine ist bisher als zweidimensionale (Kara) bzw. Zwei-Band-Turingmaschine (MPG-Simulator) konzipiert. Um von einem universellen Berechnungsmodell sprechen zu können, müsste die universelle Turingmaschine vom selben Typ wie die zu simulierenden Turingmaschinen sein (also eine Ein-Band-Turingmaschine).
Zweidimensionale
Turingmaschine
/
Zwei-Band-Turingmaschine
68 Äquivalenzsatz
Satz: Eine Funktion f: N x N x ... x N N ist mit einer Ein-Band-Turingmaschine berechenbar gdw sie mit einer Zwei-Band-Turingmaschine berechenbar istgdwsie mit einer Mehr-Band-Turingmaschine berechenbar istgdwsie mit einer zweidimensionalen Turingmaschine berechenbar ist.
Beweisidee: Simulation
siehe etwa: U. Mayr: Theoretische Informatik am PC. (Programm: Bsp-a5.tm)
Beweisidee: Simulation
siehe etwa: U. Mayr: Theoretische Informatik am PC. (Programm: Bsp-a5.tm)
69
Existenz universeller Turingmaschinen
Satz: Es gibt universelle Turingmaschinen.
Bemerkungen zum Beweis:
Die Existenz einer universellen Turingmaschine zeigt man, indem man eine TM konstruiert, die sich wie ein Turingmaschinen-Interpreter verhält, d. h. diese (zweidimensionale oder Mehr-Band-) Turingmaschine simuliert das Verhalten einer beliebig vorgegebenen Ein-Band-Turingmaschine bei einer beliebig vorgegebenen Bandbelegung. Die vorgegebene Turingmaschine und die vorgegebene Bandbelegung müssen dabei geeignet kodiert werden.
70 Zwischenbilanz
Was leistet das Berechnungsmodell "Turingmaschine"?Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Was leistet das Berechnungsmodell "Turingmaschine"?Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Bemerkung:Die Turingmaschine ist damit trotz ihrer Einfachheit ein ernst zu nehmender Kandidat für die Präzisierung der "Idee Computer".
71 Teil 5
Alternative Berechnungsmodelle
72 Maschinenorientierte Modelle
Die Turingmaschine ist letztlich eine mathematische Präzisierung des "Prozessors". Hier wird eine Art Modell-Maschine festgelegt, die die "Idee Computer" erfassen soll. Weitere Modell-Maschinen sind möglich.
Die Turingmaschine ist letztlich eine mathematische Präzisierung des "Prozessors". Hier wird eine Art Modell-Maschine festgelegt, die die "Idee Computer" erfassen soll. Weitere Modell-Maschinen sind möglich.
Maschinenorientierter Ansatz: Präzisierung des ProzessorsBeispiele: Turingmaschine, Registermaschine
Anweisungsorientierter Ansatz: Präzisierung der zulässigen Anweisungen
Zuordnungsorientierter Ansatz: Präzisierung der E/A-Zuordnungen
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
73 Registermaschine
Das Registermaschinenmodell orientiert sich stärker am Aufbau realer Computer.Das Registermaschinenmodell orientiert sich stärker am Aufbau realer Computer.
> 0 JMP 3 1 INC 0 2 DEC 1 3 TST 1 4 JMP 1 5 HLT
0: 51: 32: 03: 04: 0..
ProgrammDaten
> x INC i Erhöhe Register i um 1. Gehe zu Zeile x+1.
> x DEC i Erniedrige Register i um 1. Gehe zu Zeile x+1.
> x JMP i Gehe zu Zeile i.
> x TST iWenn Register i ungleich 0 ist, dann gehe zu Zeile x+1, sonst zu Zeile x+2.
> x HLT Beende die Bearbeitung.
74 Aufgabe
Entwickeln Sie ein Registermaschinenprogramm, das den Inhalt eines Registers verdoppelt: Entwickeln Sie ein Registermaschinenprogramm, das den Inhalt eines Registers verdoppelt:
0: 01: n2: 03: 04: 0..
Zustand vorher
RM-Programm
0: 2n1: 02: 03: 04: 0..
Zustand nachher
75 Berechenbarkeit
Definition: Eine Funktion f: N N heißt Registermaschinen-berechenbar, gdw gilt: Es gibt eine Registermaschine mit der folgenden Eigenschaft
AZ: Im Registern R1 befindet sich der Ausgangswert.
ZZ: Fall 1: f(n) ist definiert:Die RM hält und in R0 befindet sich der Ergebniswert.
Fall 2: f(n) ist undefiniert:Die RM hält nicht.
Analog für f: N x N x ... x N N
0 n 0 0 ...
... ...f(n)
... ...
76 Berechenbarkeit
0: 01: n2: 03: 04: 0..
Zustand vorher
RM-Programm
0: 2n1: 02: 03: 04: 0..
Zustand nachher
Das RM-Programm oben zeigt, dass die Funktion f: N N mit f(n) = 2n Registermaschinen-berechenbar ist.
> 0 JMP 4 1 DEC 1 2 INC 0 3 INC 2 4 TST 1 5 JMP 1 6 JMP 10 7 DEC 2 8 INC 0 9 TST 2 10 JMP 7 11 HLT
77 Ergebnisse
Satz: Die folgenden Funktionen sind Registermaschinen-berechenbar:f(n) = 2nf(m, n) = m + nf(m, n) = IF(mn, m-n, )f(m, n) = mn...
78 Äquivalenzsatz
Satz: Eine Funktion f: N x N x ... x N N ist Turingmaschinen-berechenbar gdw sie Registermaschinen-berechenbar ist.
Bemerkungen zum Beweis:
Der Beweis wird konstruktiv geführt. Man konstruiert mit Hilfe einer Turingmaschine einen Registermaschinen-Interpreter und umgekehrt mit Hilfe einer Registermaschine einen Turingmaschinen-Interpreter.
79 Anweisungsorientierte Modelle
Die Grundidee anweisungsorientierter Berechnungsmodelle besteht darin, die erlaubten Anweisungen über eine Programmiersprache festzulegen.
Die Grundidee anweisungsorientierter Berechnungsmodelle besteht darin, die erlaubten Anweisungen über eine Programmiersprache festzulegen.
Maschinenorientierter Ansatz: Präzisierung des Prozessors
Anweisungsorientierter Ansatz: Präzisierung der zulässigen AnweisungenBeispiele: LOOP, WHILE, PASCAL, DELPHI, JAVA, PYTHON, ...
Zuordnungsorientierter Ansatz: Präzisierung der E/A-Zuordnungen
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
80 LOOP-Programme / Syntax
Bestandteile von LOOP-Programmen:Bestandteile von LOOP-Programmen:
Variablen: x0 x1 x2 ...
Konstanten: 0 1 2 ...
Trennsymbole: ; :=
Operatoren: + -
Schlüsselwörter: LOOP DO END
Jede Wertzuweisung der Form xi := c oder xi := xj oder xi := xj + c oder xi := xj - c ist ein LOOP-Programm.
Falls P1 und P2 LOOP-Programme sind, dann ist auch die Sequenz P1; P2 ein LOOP-Programm.
Falls P ein LOOP-Programm ist, dann ist auch LOOP xi DO P END ein LOOP-Programm.
Aufbau eines LOOP-Programms:Aufbau eines LOOP-Programms:
81 LOOP-Programme / Semantik
Ausführung der LOOP-AnweisungAusführung der LOOP-Anweisung
Eine LOOP-Anweisung der Form LOOP xi DO P END wird wie folgt ausgeführt: Die LOOP-Anweisung P wird sooft ausgeführt, wie der Wert der Variablen xi zu Beginn beträgt.
x0 := x1; LOOP x2 DO x0 := x0 + 1 END
Beispiel eines LOOP-Programms
{x0: [...]; x1: [5]; x2: [3]; x3: [...]; ... }
x0 := x1; LOOP x2 DO x0 := x0 + 1 END
{x0: [8]; x1: [5]; x2: [3]; x3: [...]; ... }
Bedeutung eines LOOP-ProgrammsBedeutung eines LOOP-Programms
Das Programm berechnet die Additionsfunktion auf natürlichen Zahlen: f(m, n) = m + n
x0 = x1 for i in range(x2): x0 = x0 + 1
Entsprechendes Python-Programm
82 WHILE-Programme / Syntax
Bestandteile von WHILE-Programmen:Bestandteile von WHILE-Programmen:
Variablen: x0 x1 x2 ...
Konstanten: 0 1 2 ...
Trennsymbole: ; :=
Operatoren: + -
Schlüsselwörter: WHILE DO END
Jede Wertzuweisung der Form xi := c oder xi := xj oder xi := xj + c oder xi := xj - c ist ein WHILE-Programm.
Falls P1 und P2 WHILE-Programme sind, dann ist auch die Sequenz P1; P2 ein WHILE-Programm.
Falls P ein WHILE-Programm ist, dann ist auch WHILE xi 0 DO P END ein WHILE-Programm.
Aufbau eines LOOP-Programms:Aufbau eines LOOP-Programms:
83 WHILE-Programme / Semantik
Ausführung der WHILE-AnweisungAusführung der WHILE-Anweisung
Eine WHILE-Anweisung der Form WHILE xi 0 DO P END wird wie folgt ausgeführt: Das WHILE-Programm P wird solange ausgeführt, wie der Wert der Variablen xi ungleich Null ist.
x0 := x1; WHILE x2 0 DO x0 := x0 + 1; x2 := x2 - 1 END
Beispiel eines WHILE-Programms
{x0: [0]; x1: [5]; x2: [3]; x3: [0]; ... }
x0 := x1; WHILE x2 0 DO x0 := x0 + 1; x2 := x2 - 1 END
{x0: [8]; x1: [5]; x2: [0]; x3: [0]; ... }
Bedeutung eines LOOP-ProgrammsBedeutung eines LOOP-Programms
Das Programm berechnet die Additionsfunktion auf natürlichen Zahlen: f(m, n) = m + n
x0 = x1 while x2 <> 0: x0 = x0 + 1 x2 = x2 - 1
Entsprechendes Python-Programm
84 Berechenbarkeit
Definition: Eine Funktion f: N N heißt LOOP-/WHILE-berechenbar, gdw gilt: Es gibt ein LOOP-/WHILE-Programm mit der Eigenschaft:
AZ: Die Variable x1 enthält den Ausgangswert:
{x0: [0]; x1: [n]; x2: [0]; x3: [0]; ... }
ZZ: Fall 1: f(n) ist definiert:Die Ausführung des Programms endet und x0 enthält den Ergebniswert.
{x0: [f(n)]; x1: [...]; x2: [...]; x3: [...]; ... }
Fall 2: f(n) ist undefiniert:Die Ausführung des Programms endet nicht.
Analog für f: N x N x ... x N N
85 Aufgabe
Entwickeln Sie ein LOOP-Programm / WHILE-Programm zur Berechnung der Verdopplungsfunktion / Multiplikationsfunktion. Testen Sie das jeweilige Programm mit einer entsprechenden Python-Implementierung.
86 Aufgabe
Welche Funktion wird durch das folgende WHILE-Programm berechnet?
x0 := x1;
WHILE x2 0 DO x0 := x0 + 1 END
Gibt es Funktionen, die mit keinem LOOP-Programm berechnet werden können?
87 Ergebnisse
Satz: Es gibt Funktionen f: N x N x ... x N N, die WHILE-berechenbar, aber nicht LOOP-berechenbar sind.
Die Ausführung jedes LOOP-Programms endet immer. Ein WHILE-Programm kann dagegen eine Endlosschleife enthalten.
x0 := x1;
WHILE x2 0 DO x0 := x0 + 1 END
Satz: Die folgenden Funktionen sind WHILE-berechenbar: f(n) = 2nf(m, n) = m + nf(m, n) = IF(mn, m-n, )f(m, n) = mn...
88 Äquivalenzsatz
Satz: Eine Funktion f: N x N x ... x N N ist WHILE-berechenbar gdw sie Registermaschinen-berechenbar ist.
Bemerkungen zum Beweis:
Der Beweis wird konstruktiv geführt. Man konstruiert zu jeder Registermaschine ein entsprechendes WHILE-Programm und umgekehrt zu jedem WHILE-Programm eine entsprechende Registermaschine.
89 Zuordnungsorientierte Modelle
Grundidee: Man beschreibt die berechenbaren E/A-Zuordnungen wie folgt: Einige einfache Grundfunktionen werden als „berechenbar“ erklärt. Des weiteren werden einige einfache Konstruktionsprinzipien angegeben, die beschreiben, wie man aus „berechenbaren Funktionen“ weitere „berechenbare Funktionen“ erhält. Die zentrale Konstruktionsoperation ist dabei die Rekursion.
Grundidee: Man beschreibt die berechenbaren E/A-Zuordnungen wie folgt: Einige einfache Grundfunktionen werden als „berechenbar“ erklärt. Des weiteren werden einige einfache Konstruktionsprinzipien angegeben, die beschreiben, wie man aus „berechenbaren Funktionen“ weitere „berechenbare Funktionen“ erhält. Die zentrale Konstruktionsoperation ist dabei die Rekursion.
Maschinenorientierter Ansatz: Präzisierung des Prozessors
Anweisungsorientierter Ansatz: Präzisierung der zulässigen Anweisungen
Zuordnungsorientierter Ansatz: Präzisierung der E/A-ZuordnungenBeispiele: primitiv rekursive Funktionen, partiell rekursive Funktionen
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
90 Rekursive Berechnungsschemata
Bemerkungen:Bemerkungen:
Die Nachfolgerfunktion s: N N, die jeder natürlichen Zahl ihren direkten Nachfolger zuordnet, wird als gegebene berechenbare Funktion betrachtet.
Die Funktion add: N x N N, die je zwei natürlichen Zahlen ihre Summe zuordnen soll, wird rekursiv festgelegt: - Zunächst wird der Rekursionsanfang „addiere zur Zahl x die Zahl 0“ festgelegt. - Anschließend wird der Fall „addiere zur Zahl x den Nachfolger s(y) einer Zahl y“ auf den Fall „addiere zu x die Zahl y“ rekursiv reduziert.
Bei der Festlegung werden hier die Konstruktionsoperationen „Rekursion“ und „Funktionskomposion“ und die Grundfunktion „s“ benutzt.
add(x,0) = xadd(x,s(y))= s(add(x,y))
Beispiel: Addition natürlicher Zahlen
add(3,2)= s(add(3,1))= s(s(add(3,0)))= s(s(3))= s(4)= 5
Beispiel: Berechnung einer Addition
91 Implementierung mit Python
ImplementierungImplementierung
add(x,0) = xadd(x,s(y))= s(add(x,y))
Beispiel: Addition natürlicher Zahlen
add(3,2)= s(add(3,1))= s(s(add(3,0)))= s(s(3))= s(4)= 5
Beispiel: Berechnung einer Addition
def s(x): return x+1
def p(x): return x-1
def add(x, y): if y == 0: return x else: return s(add(x, p(y)))
>>> add(3, 2)5
92 Aufgabe
Entwickeln Sie rekursive Berechnungsschemata für die folgenden Funktionen. Benutzen Sie nur die vorgegebene Nachfolgerfunktion s und bereits definierte Funktionen (wie add).
mult(x, y) Beschreibt die übliche Multiplikation natürlicher Zahlen
fakt(x) Beschreibt die Fakultätsfunktion:f(0) = 1, f(1) = 1, f(2) = 2*1, f(3) = 3*2*1, ...
exp(x, y) Beschreibt die Potenzbildung für natürliche Zahlen, d. h.:exp(2, 3) = 23
93 Aufgabe
Untersuchen Sie die folgenden rekursiven Berechnungsschemata und beschreiben Sie die jeweils berechneten Funktionen.
test(0)=1test(s(x))=0
pred(0)=0pred(s(x))=x
subtr(x,0)=xsubtr(x,s(y))=pred(subtr(x,y))
absdiff(x,y)=add(subtr(x,y),subtr(y,x))
equal(x,y)=test(absdiff(x,y))
94 Aufgabe
Welche Berechnungsschemata sind korrekt, sinnvoll?
subtr2(x, 0) = xsubtr2(0, y) = ysubtr2(s(x), s(y)) = subtr2(x, y)
subtr3(x, 0) = xsubtr3(0, y) = ysubtr3(x, y) = subtr3(s(x), s(y))
add2(x, 0) = xadd2(x,y)= add(s(x),pred(y)))
95 Primitive Rekursion
Beispiel für ein primitives Reduktionsschema:Beispiel für ein primitives Reduktionsschema:
add(x,0) = xadd(x,s(y))= s(add(x,y))
Rekursionsanfang: Die Funktion f kommt nicht auf der rechten Seite vor.
Rekursionsschritt: Die Funktion f kommt auf der rechten Seite vor, ein Argument wird dabei um 1 reduziert.
VerallgemeinerungVerallgemeinerung
f(x1,...,xn,0) = g(x1,...,xn)f(x1,...,xn,s(y)) = h(x1,...,xn,y,f(x1,...,xn,y))
96 Primitiv rekursive Funktionen
Definition: Eine Funktion f: N x ... x N N heißt primitiv rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition und primitiver Rekursion als Konstruktionsoperationen berechnen.
Satz: Die folgenden Funktionen sind primitiv rekursiv: f(n) = 2nf(m, n) = m + nf(m, n) = mn...
97 Aufgabe
Ack(0,y)=s(y) Ack(s(x),0)=Ack(x,1)Ack(s(x),s(y))=Ack(x,Ack(s(x),y))
Testen Sie das folgende rekursive Berechnungsschemata zur sogenannten Ackermann-Funktion. Was beobachtet man, wenn die Parameter (insbesondere der zweite) nicht sehr klein gewählt werden?
98 Ackermann-Funktion
Ack(0,y)=s(y) Ack(s(x),0)=Ack(x,1)Ack(s(x),s(y))=Ack(x,Ack(s(x),y))
Rekursive Definition:
Beachte: Es handelt sich hier nicht um ein primitiv rekursives Rekursionsschema.
Satz: Die Ackermann-Funktion ist nicht primitiv rekursiv.
Bemerkung:Man muss zeigen, dass die Ackermannfunktion sich nicht mit Hilfe eines primitiv rekursiven Rekursionsschemas darstellen lässt. Zum Beweis zeigt man, dass die Ackermann-Funktion schneller wächst als jede primitiv rekursive Funktion.
99 Aufgabe
f(x, y) = „das kleinste z mit y+z=x“
Wir betrachten die folgende informell definierte Funktion. Berechnen Sie f(5, 2) und f(2, 5). Beschreiben Sie das Verhalten der Funktion f.
100 Primitiv rekursive Funktionen
Definition: Eine Funktion f: N x ... x N N heißt partiell rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition, primitiver Rekursion und dem „das kleinste“-Operator als Konstruktionsoperationen berechnen.
Satz: Die Ackermann-Funktion ist partiell rekursiv.
Beweis: siehe Fachliteratur
101 Äquivalenzsatz
Satz: Eine Funktion f: N x N x ... x N N ist primitiv rekursiv gdw sie LOOP-berechenbar ist.
Eine Funktion f: N x N x ... x N N ist partiell rekursiv gdw sie WHILE-berechenbar ist.
Beweis: siehe Fachliteratur
102 Zusammenfassung
Satz (Äquivalenz von Berechnungsmodellen): Gegeben sei eine Funktion f: N x N x ... x N N. Die folgenden Aussagen sind äquivalent:
- f ist Turingmaschinen-berechenbar.
- f ist Registermaschinen-berechenbar.
- f ist WHILE-berechenbar,
- f ist partiell rekursiv.
- f ist Pascal-berechenbar.
- ...
103 Zusammenfassung
Maschinenorientierter Ansatz: Präzisierung des Prozessors
Anweisungsorientierter Ansatz: Präzisierung der zulässigen Anweisungen
Zuordnungsorientierter Ansatz: Präzisierung der E/A-Zuordnungen
“Prozessor”Verarbeitungsanweisungen
Eingaben
Ausgaben
Alle bisher gewählten Ansätze zur Präzisierung der "Grundidee Computer" führen auf dieselbe Klasse berechenbarer Funktionen.
104 Church-Turing-These
These: Die Klasse der im intuitiven Sinn berechenbaren Funktion ist genau die Klasse der Turingmaschinen-berechenbaren Funktionen bzw. die Klasse der partiell rekursiven Funktionen bzw. die Klasse der WHILE-berechenbaren Funktionen bzw. ...
Anwendung:Oben wurde gezeigt, dass das Halteproblem nicht Python-entscheidbar ist. Mit der Church-Turing-These ergibt sich hieraus, dass das Halteproblem algorithmisch nicht entscheidbar ist.
Was leistet das Berechnungsmodell "Turingmaschine" / "Python-programmierbar" / ...?Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
Was leistet das Berechnungsmodell "Turingmaschine" / "Python-programmierbar" / ...?Es soll die „Idee Computer“ erfassen, d. h. es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann
105 Teil 6
Grenzen der Berechenbarkeit
106 Problem
Ist jede Funktion f: N N (Turingmaschinen-) berechenbar?
Menge der Funktionen von N nach N
Menge der berechenbaren
Funktionen von N nach N
?
?
n 2n
n s(n)
n prim(n)
107 Abzählverfahren
Es gibt nur endlich viele Turingmaschinen mit 1 Zustand. Diese können der Reihe nach abgezählt (durchnummeriert) werden.
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000
Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000
Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000
Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000
Z000 ' ' 'I' L Z000Z000 'I' ' ' L Z000
...
0
1
2
3
4
108 Aufgabe
Ergänzen Sie die begonnene Abzählung um weitere Turingmaschinen mit genau einem Zustand. Wie viele gibt es insgesamt?
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000
Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000
Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000
Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000
Z000 ' ' 'I' L Z000Z000 'I' ' ' L Z000
...
0
1
2
3
4
109 Abzählverfahren
Es gibt nur endlich viele Turingmaschinen mit 2 Zuständen. Diese können ebenfalls der Reihe nach abgezählt werden.
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' R Z000
...
0
110 Abzählverfahren
Die gesamte Menge der Turingmaschinen kann abgezählt werden, indem man zunächst die mit 1 Zustand durchnummeriert, dann die mit 2 Zuständen u.s.w..
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000
Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000
...
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' R Z000
...
0
1
..
36
111 AbzählbarkeitDefinition: Eine Menge M heißt abzählbar genau dann, wenn es eine Abbildung von den natürlichen Zahlen N in M gibt, bei der alle Elemente aus M als Bildelemente natürlicher Zahlen erfasst werden.
Satz: Die Menge der Turingmaschinen (über dem Eingabealphabet {'I'}) ist abzählbar.
D. h., die Turingmaschinen lassen sich durchnummerieren:
T0; T1; T2; ...
D. h., die Elemente von M können durchnummeriert werden. Alle Elemente aus M müssen bei der Nummerierung erfasst werden. Wiederholungen sind bei der Nummerierung zugelassen.
112 Abzählverfahren
Wir streichen jetzt alle Turingmaschinen, die keine Funktion f: N N berechnen. Die verbleibenden Turingmaschinen entsprechen genau den Turing-berechenbaren Funktionen.
f0: n
f1: n
f2: 0 0 n n-1 (n > 0)
...
Keine Funktion
Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000
Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000
Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000
...
Z000 ' ' ' ' R Z000Z000 'I' 'I' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' S Z000
0
1
2
..
x
113 Abzählbarkeit
Satz: Die Menge der Turingmaschinen-berechenbaren Funktion f: N N ist abzählbar.
Menge der Funktionen von N nach N
Menge der berechenbaren
Funktionen von N nach N
?
?
f0, f1, f2, f3, ...
114
Existenz nicht-berechenbarer Funktionen
Definition einer neuen Funktion f: N NDefinition einer neuen Funktion f: N N
f(0) = f0(0)+1, falls f0(0) definiert ist, sonst f(0) = 0
f(1) = f1(1)+1, falls f1(1) definiert ist, sonst f(1) = 0
f(2) = f2(2)+1, falls f2(2) definiert ist, sonst f(2) = 0
f(3) = f3(3)+1, falls f3(3) definiert ist, sonst f(3) = 0
...
f(n) = fn(n)+1, falls fn(n) definiert ist, sonst f(n) = 0
...
f f0
f f1
f f2
f f3
...
f f0
...
Die Funktion f: N N unterscheidet sich von allen berechenbaren Funktionen, kann also selbst nicht berechenbar sein.
Die Funktion f: N N unterscheidet sich von allen berechenbaren Funktionen, kann also selbst nicht berechenbar sein.
115
Existenz nicht-berechenbarer Funktionen
Satz: Es gibt Funktionen f: N N, die nicht (Turingmaschinen-) berechenbar sind.
Menge der Funktionen von N nach N
Menge der berechenbaren
Funktionen von N nach N
f
?
f0, f1, f2, f3, ...
116
Existenz nicht-berechenbarer Funktionen
Menge der Funktionen von N nach N
Menge der berechenbaren
Funktionen von N nach N
?
f0, f1, f2, f3, ...
Ziel ist es, eine nicht-berechenbare Funktion konkret zu beschreiben.
Rado´sche -Funktion
117 Biber-Turingmaschinen
Eine Biber-TM ist eine eindimensionale TM, die in jedem Arbeitsschritt genau eine "Baumaktion" durchführt (Baumstamm hinlegen oder wegnehmen) und einen Schritt nach rechts oder links geht.
Eine Biber-TM startet in einer leeren Welt, erzeugt „Baumstämme“ und hält nach endlich vielen Arbeitsschritten.
Vorher:
Nachher:
Biber-TM:
118 Aufgabe
Biberwettbewerb:
Gesucht ist eine Biber-TM mit genau 2 Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme erzeugt, bevor sie hält. Eine solche TM heißt „fleißiger Biber“ (mit 2 Zuständen) bzw. „busy beaver TM“.
Gesucht ist eine Biber-TM mit genau 3 (bzw. 4) Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme erzeugt, bevor sie hält. Eine solche TM heißt „fleißiger Biber“ (mit 3 bzw. 4 Zuständen) bzw. „busy beaver TM“.
119 Fleißige Biber
alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand
Z0 I I L Z1Z0 ' ' I R Z1
Z1 I I S Z0Z1 ' ' I L Z0
alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand
Z0 I I L Z2Z0 ' ' I R Z1
Z1 I I S Z1Z1 ' ' I L Z0
Z2 I I S Z2Z2 ' ' I L Z1
Fleißiger Biber mit 2 Zuständen: Fleißiger Biber mit 2 Zuständen:
Fleißiger Biber mit 3 Zuständen: Fleißiger Biber mit 3 Zuständen:
120 Rado´sche Σ-Funktion
Definition (Tibor Rado, 1962): Die Funktion : N N ist wie folgt festgelegt: (n) bezeichne die maximale Anzahl von Baumstämmen, die eine Biber-TM mit genau n Zuständen (außer dem Stop-Zustand) erzeugen kann.
n
0
1
2
3
4
5
6
...
(n)
0
1
4
6
13
4098
95524079
...
121 Satz von Rado
SatzDie Rado´sche -Funktion ist nicht Turingmaschinen-berechenbar.
Beweis:
Der Beweis benutzt die folgenden (leicht zu zeigenden) Eigenschaften der -Funktion:
(n) n für alle n N,
(n) < (n+1) für alle n N (Monotonie von ).
Der Beweis wird durch Widerspruch geführt. Annahme: Es gibt eine Turingmaschine T, mit der berechnet werden kann. Die Anzahl der Zustände von T bezeichnen wir mit k.
AZ: II
ZZ: I I II
z0T :
122 Satz von Rado
Man zeigt zunächst, dass es eine Turingmaschine Tn mit n+1 Zuständen (außer dem Stop-Zustand) gibt, der auf einem leeren Band eine Baumstammreihe mit genau n Baumstämmen erzeugt:
AZ:
ZZ: I I
z0T2:
Man zeigt anschließend, dass es eine Turingmaschine TV mit 6 Zuständen (außer dem Stop-Zustand) gibt, der eine gegebene, beliebig lange Baumstammreihe verdoppelt:
AZ:
ZZ: I I
z0TV:
II
I I
123 Satz von Rado
Tn: erzeugt eine Baumstammreihe der Länge n
Wir verknüpfen die 3 Turingmaschinen jetzt wie folgt zu einer neuen Turingmaschine Tn,V, :
AZ:
ZZ: I I
z0
ZZ: I I
TV: erzeugt eine Baumstammreihe der Länge 2n
I I
ZZ: I I
T : erzeugt eine Baumstammreihe der Länge (2n)
I I II I I ...
Beachte: Tn,V, hat n+7+k Zustände und erzeugt eine Baumstammreihe der Länge (2n).
124 Satz von Rado
Wir vergleichen jetzt diese zusammengesetzte Turingmaschine Tn,V, mit einem fleißigen Biber TFB(n+7+k) mit n+7+k Zuständen:
Tn,V, hat n+7+k Zustände und erzeugt (2n) Baumstämme.
TFB(n+7+k) hat n+7+k Zustände und erzeugt (n+7+k) Baumst
Da ein fleißiger Biber die maximal mögliche Anzahl von Baumstämmen erzeugt, gilt (für alle n N): (n+7+k) (2n).
Sei n = 2(7+k). Dann gilt:
n+7+k = 3(7+k)
2n = 4(7+k), also n+7+k < 2n.
Aus der Monotonie von folgt: (n+7+k) < (2n).
Es ergibt sich also ein Widerspruch. Da alle Schlüsse korrekt sind, muss die Annahme falsch sein.
125 Entscheidbarkeit
Nicht-entscheidbaren Probleme (bzw. deren zugehörige Sprachen):
Halteproblem: Kann man mit einem Algorithmus entscheiden, ob ein beliebiger Algorithmus bei der Bearbeitung von Daten hält?
Korrektheitsproblem: Kann man mit einem Algorithmus entscheiden, ob ein beliebiger Algorithmus korrekt bzgl. einer Spezifikation ist?
Wahrheitsproblem: Kann man mit einem Algorithmus entscheiden, ob eine beliebige mathematische Aussage wahr ist.
Diophantische Gleichungen: Kann man mit einem Algorithmus entscheiden, ob eine beliebige Polynomgleichung (in der verschiedene Variablen mit verschiedenen Exponenten vorkommen können) mit ganzzahligen Koeffizienten eine ganzzahlige Lösung hat?
Definition: Eine Sprache über einem Alphabet heißt (Turing-) entscheidbar, wenn es einen Algorithmus (als Turingprogramm) gibt, der für jedes Wort über dem Alphabet feststellt, ob es zur Sprache gehört.
126 Semi-EntscheidbarkeitDefinition: Eine Sprache über einem Alphabet heißt semi-entscheidbar, wenn es einen Algorithmus gibt, der für jedes Wort über dem Alphabet, das zur Sprache gehört, dies auch mitteilt.
Algorithmus zur Lösung Diophantischer Gleichungen:
Eingabe: Gleichung; z. B.: x3 + 5x2y2z – xz + 37 = 0
Probiere systematisch alle möglichen Belegungen der in der Gleichung vorkommenden Variablen aus, ob sie die Gleichung erfüllen. Stoppe, wenn eine passende Belegung gefunden wurde. Im Beispiel:
x = 0; y = 0; z = 0: neinx = 1; y = 0; z = 0: neinx = -1; y = 0; z = 0 neinx = 0; y = 1; z = 0 nein...x = 1; y = 2; z = -2 ja
Ausgabe: Lösbarkeit; im Beispiel: ja
Beachte: Der Algorithmus liefert nur in den Fällen, in denen eine Lösung existiert, ein positives Ergebnis, in anderen Fällen hält er nicht.
Beachte: Der Algorithmus liefert nur in den Fällen, in denen eine Lösung existiert, ein positives Ergebnis, in anderen Fällen hält er nicht.
127 Teil 7
Ein Blick in die Geschichte
128 David Hilbert
129 Hilbert´s Rede
Wer von uns würde nicht gern den Schleier lüften, unter dem die Zukunft verborgen liegt, um einen Blick zu werfen auf die bevorstehenden Fortschritte unsrer Wissenschaft und in die Geheimnisse ihrer Entwickelung während der künftigen Jahrhunderte! Welche besonderen Ziele werden es sein, denen die führenden mathematischen Geister der kommenden Geschlechter nachstreben? welche neuen Methoden und neuen Thatsachen werden die neuen Jahrhunderte entdecken - auf dem weiten und reichen Felde mathematischen Denkens?
Die Geschichte lehrt die Stetigkeit der Entwickelung der Wissenschaft. Wir wissen, daß jedes Zeitalter eigene Probleme hat, die das kommende Zeitalter löst oder als unfruchtbar zur Seite schiebt und durch neue Probleme ersetzt. Wollen wir eine Vorstellung gewinnen von der muthmaßlichen Entwickelung mathematischen Wissens in der nächsten Zukunft, so müssen wir die offenen Fragen vor unserem Geiste passiren lassen und die Probleme überschauen, welche die gegenwärtige Wissenschaft stellt, und deren Lösung wir von der Zukunft erwarten. Zu einer solchen Musterung der Probleme scheint mir der heutige Tag, der an der Jahrhundertwende liegt, wohl geeignet; denn die großen Zeitabschnitte fordern uns nicht blos auf zu Rückblicken in die Vergangenheit, sondern sie lenken unsere Gedanken auch auf das unbekannte Bevorstehende.
[...]
130 Hilbert´s Rede
2. Die Widerspruchslosigkeit der arithmetischen Axiome
Wenn es sich darum handelt, die Grundlagen einer Wissenschaft zu untersuchen, so hat man ein System von Axiomen aufzustellen, welche eine genaue und vollständige Beschreibung derjenigen Beziehungen enthalten, die zwischen den elementaren Begriffen jener Wissenschaft stattfinden. Die aufgestellten Axiome sind zugleich die Definitionen jener elementaren Begriffe und jede Aussage innerhalb des Bereiches der Wissenschaft, deren Grundlagen wir prüfen, gilt uns nur dann als richtig, falls sie sich mittelst einer endlichen Anzahl logischer Schlüsse aus den aufgestellten Axiomen ableiten läßt. Bei näherer Betrachtung entsteht die Frage, ob etwa gewisse Aussagen einzelner Axiome sich untereinander bedingen und ob nicht somit die Axiome noch gemeinsame Bestandteile enthalten, die man beseitigen muß, wenn man zu einem System von Axiomen gelangen will, die völlig von einander unabhängig sind.Vor Allem aber möchte ich unter den zahlreichen Fragen, welche hinsichtlich der Axiome gestellt werden können, dies als das wichtigste Problem bezeichnen, zu beweisen, daß dieselben untereinander widerspruchslos sind, d.h. daß man auf Grund derselben mittelst einer endlichen Anzahl von logischen Schlüssen niemals zu Resultaten gelangen kann, die miteinander in Widerspruch stehen.
[...]
131 Hilbert´sches Programm
Widerspruchsfreiheit:Die Formalisierung soll widerspruchsfrei sein (d. h.: keine zwei sich ausschließenden Aussagen können hergeleitet werden).
Vollständigkeit:Jede wahre mathematische Aussage kann hergeleitet werden.
Entscheidbarkeit:Es gibt ein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.
Hilbert´sches Programm: Formalisierung der Mathematik
132 Hilbert´sches Programm
Widerspruchsfreiheit:Die Formalisierung soll widerspruchsfrei sein (d. h.: keine zwei sich ausschließenden Aussagen können hergeleitet werden).
Vollständigkeit:Jede wahre mathematische Aussage kann hergeleitet werden.
Entscheidbarkeit:Es gibt ein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.
Hilbert´sches Programm: Formalisierung der Mathematik
Das Hilbert´sche Entscheidungsproblem verlangt den Nachweis, dass es einen Algorithmus gibt, mit dessen Hilfe man die Wahrheit mathematischer Aussagen "berechnen" kann.
133 Ergebnisse von Gödel
Widerspruchsfreiheit:Die Formalisierung soll widerspruchsfrei sein (d. h.: keine zwei sich ausschließenden Aussagen können hergeleitet werden).
Vollständigkeit:Jede wahre mathematische Aussage kann hergeleitet werden.
Entscheidbarkeit:Es gibt ein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.
Gödelsche Unvollständigkeitssätze (1931)In jedem formalen System, das widerspruchsfrei ist, existieren Aussagen, die wahr sind, aber innerhalb des Systems nicht hergeleitet werden können. Das bedeutet, es bleiben immer wahre Aussagen übrig, die nicht herleitbar sind. Wenn ein formales System widerspruchsfrei ist, dann kann man innerhalb des Systems nicht herleiten, dass es widerspruchsfrei ist.
134 Ergebnisse von Church und Turing
Widerspruchsfreiheit:Die Formalisierung soll widerspruchsfrei sein (d. h.: keine zwei sich ausschließenden Aussagen können hergeleitet werden).
Vollständigkeit:Jede wahre mathematische Aussage kann hergeleitet werden.
Entscheidbarkeit:Es gibt kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.
Church / Turing (1936)Es gibt kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht.
135 Ergebnisse von Church und Turing
Church / Turing (1936)Es gibt kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht.
Um nachzuweisen, dass es keinen Algorithmus zur Entscheidung über den Wahrheitsgehalt mathematischer Aussagen gibt, musste zunächst präzisiert werden, was ein Algorithmus ist.
Turing führte zu diesem Zweck die später nach ihm benannte Turingmaschine ein, Church entwickelte unabhängig hiervon eine zuordnungsbasierte Präzisierung. Beide Präzisierungen wurden später als gleichwertig erkannt.
Interessant ist in diesem Zusammenhang auch, dass die "Idee Computer" präzisiert wurde, bevor die ersten praktikablen Computer gebaut wurden.
136 Ein Blick über den Zaun
Informatik: Methode: Ein Problem mit Hilfe eines Algorithmus lösen. Grenze der Methode: Das Entscheidungsproblem (...
Halteproblem ...) ist algorithmisch nicht lösbar. (Turing) Mathematik:
Methode: Einen Satz beweisen. Grenze der Methode: In jedem formalen System, das
widerspruchsfrei ist, existieren Aussagen, die wahr sind, aber innerhalb des Systems nicht hergeleitet werden können. Das bedeutet, es bleiben immer wahre Aussagen übrig, die nicht beweisbar sind. (Gödel)
Physik: Methode: Eigenschaften eines Systems messen. Grenze der Methode: Man kann Ort und Impuls eines
Teilchens nicht gleichzeitig exakt bestimmen. (Heisenberg)
137 Literaturhinweise
U. Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag 2001.
Gasper, Leiß, Spengler, Stimm: Technische und theoretische Informatik. Bayerischer Schulbuch-Verlag 1992.
Reichert, Nievergelt, Hartmann: Programmieren mit Kara. Springer-Verlag 2004.
D. Harel: Das Affenpuzzle und weitere bad news aus der Computerwelt. Springer-Verlag 2002.
J. Casti: Das Cambridge Quintett. Berlin Verlag 1998.
D. R. Hofstadter: Gödel, Escher, Bach. Klett-Cotta 1985.