Flashcards
Berechenbarkeit und Komplexität
Cards in this deck (21)
- 1AlgorithmusEndliche Beschreibung eines mechanischen Verfahrens zur Lösung eines Problems
- 2David HilbertGlaubte, dass sich die ganze Mathematik in einem formalen System axiomatisieren lässt und die Frage nach der mathematischen Wahrheit einer Aussage algorithmisch entschieden werden kann.
- 3Was zeigten Kurt Gödels Unvollständigkeitssätze?Dass das von David Hilbert vorgeschlagene Programm nicht realisiert werden kann.
- 4Gültigkeit in der PrädikatenlogikChurch und Turing haben gezeigt, dass die Frage nach der Gültigkeit in der Prädikatenlogik erster Stufe nicht algorithmisch entschieden werden kann.
- 5Definition Turingmaschine
- 6Was bedeutet das Folgende? δ(z, a) = (z’, b, x)Wenn sich die Maschine in Zustand z befindet und das Zeichen a liest, geht sie im nächsten Schritt in Zustand z' über und überschreibt das Zeichen a mit b, wobei a und b Elemente des Arbeitsalphabets Г sind. Danach bewegt sich der Schreib-Lese-Kopf nach links, rechts oder gar nicht (x = L, R, N)
- 7Zustandsübergangsdiagramm für δ(z, a) = (z’, b, x)
- 8Wann ist eine Funktion f Turing-berechenbar?Falls für alle Funktionswerte f(x_1), ..., f(x_n) ein akzeptierter Zustand angenommen wird.
- 9Beispiel: binäre Nachfolgefunktion f(x) = x + 1 (Turing-Maschine)□ bezeichnet das Leerzeichen
- 10Universelle Turingmaschine (UTM)Spezielle Turingmaschine, die jede andere Turingmaschine T ausführen kann.
(Turingmaschinen-Interpreter)
Eingabe einer UTM:
Programm δ(T) von T sowie Eingabe w für T. Die UTM führt dann das Programm δ(T) mit der entsprechenden Eingabe aus. - 11Formal-mathematische Berechenbarkeitsmodelle- Turing-Maschinen
- Ungetypter Lambdakalkül (Church)
- Partiell-rekursive Funktionen (Kleene)
- Gleichheitskalküle (Gödel-Herbrand) - 12Gemeinsamkeit der Berechenbarkeitsmodelle (Theorem)Die vier erwähnten Modelle sind äquivalent, beschreiben also dieselbe Klasse von Funktionen.
- 13These von ChurchDer intuitive Algorithmusbegriff wird durch jedes der vier erwähnten formal-mathematischen Berechenbarkeitsmodelle adäquat formalisiert.
("Die vier Modelle sind korrekt") - 14Entscheidbarkeit eines ProblemsEin Problem heisst entscheidbar, wenn alle Elemente der Sprache L als Input der Turingmaschine gewählt werden können, so dass die Maschine am Ende in einen akzeptierenden Zustand gerät.
- 15Semi-Entscheidbarkeit eines ProblemsEin Problem heisst semi-entscheidbar, wenn zwar für einige Elemente der Sprache L ein akzeptierender Zustand erreicht wird, die Turinmaschine aber für andere Elemente unendlich weiter läuft, so dass wir nicht wissen, ob der Endzustand ein akzeptierender oder nicht-akzeptierender wäre.
- 16Das Halteproblem HStoppt ein beliebiges Programm x angesetzt auf eine Eingabe y nach endlich vielen Schritten?
- 17Das spezielle Halteproblem H0Stoppt ein beliebiges Programm x angesetzt auf sich selbst nach endlich vielen Schritten?
- 18Sind das Halteproblem und das spezielle Halteproblem entscheidbar?Nein, aber sie sind beide semi-entscheidbar.
- 19Der Satz von RiceDas Problem, ob eine von einem gegebenen Programm x berechnete Funktion eine gewisse, nicht-triviale Eigenschaft hat, ist unentscheidbar.
(nicht-trivial bedeutet hier, dass die Eigenschaft auf mindestens eine, nicht aber auf alle berechenbaren Funktionen zutrifft) - 20Beispiele zum Satz von RiceEs ist nicht entscheidbar, ob ein Programm x ...
... die konstante Nullfunktion berechnet
... eine überall definierte (totale) Funktion berechnet
... eine fest vorgegebene Funktion f berechnet (Spezifikationsproblem) - 211. Unvollständigkeitssatz von GödelEs bezeichne (N, +, *) die Struktur der natürlichen Zahlen mit Addition und Multiplikation. Th(N, +, *) sei die Menge aller (erststufigen) Sätze, welche in (N, +, *) wahr sind. Dann gillt:
Th(N, +, *) ist nicht semi-entscheidbar.