Sätze und Zusammenhänge
Inhaltsverzeichnis |
Aufzählbarkeit und Semi-Entscheidbarkeit
Zeitbeschränkte Berechnung
Zur Implementierung der zentralen Ideen dieses Beweises benötigen wir das Konzept zeitbeschränkter Berechnung: Beim Start einer Berechnungsaufgabe wird eine gewisse Anzahl von Ticks angegeben. Ist die betreffende Berechnung in dieser Zeit abgeschlossen, wird deren Ergebis zurück gegeben. Anderenfalls bricht die Berechnung ab. Zur Information erscheint die Ausschrift 'expired' (allerdings nicht aus auswertbarer Rückgabewert).
Aufgabe: Verändern Sie die Zahl der Ticks für die Berechnung von (fib 10) und versuchen Sie die Zeit herauszufinden, die zur Berechnung von (fib 10) mindestens benötigt wird.
Aufgabe: Zur Überprüfung Ihres experimentell ermittelten Resultats verwenden Sie die folgende Prozedur. Sie kann leicht für andere Anwendungen angepasst werden, indem man den (fib 10) entsprechend ersetzt.
Aufgrund der hier gewählten (unsichtbaren) Implementierung des Timer-Systems ist die Anzahl der erforderlichen Ticks Rechner- und Netz-unabhängig.
Aufgabe: Experimentieren Sie mit größeren Argumenten für fib, z.B. (fib 40), unter Vorgabe von lediglich 200 Ticks. Beachten Sie, dass eine Berechnung, für die die vorgegebene Zeit nicht ausreicht, automatisch abgebrochen wird.
Paarungsfunktion
Der programmtechnisch unproblematische Abbruch bei Überschreitung einer vorgegebenen Zeit ist eine wichtige Eigenschaft, die wir im Folg. bei der Implementierung der Aufzählfunktion ausnützen.
Wir verwenden die Cantorsche Paarungsfunktion:
Abzählbarkeit und Aufzählbarkeit
Aufbauschema der Wortmenge
g: A^*\mapsto \NN\setminus\{0\} wird durch die Prozedure wort->zahl berechnet.
g^{-1}: \NN\setminus\{0\}\mapsto A^* wird durch die Prozedure zahl->wort berechnet.
An welcher Position in der Menge A^* befindet sich das Wort cac?
Welches Wort steht an Position 34?
ÜA: Verändern Sie die oben eingegebenen Argumente und überprüfen Sie das jeweilige Ergebnis durch die entsprechende Umkehrfunktion.
Längenlexikografische Ordnung
Zur Definition der (zweistelligen) längenlexikografischen Ordnung ist es lediglich notwendig, die jeweils zugehörigen natürlichen Zahlen miteinander zu vergleichen (Kleinerrelation).
Entscheidbarkeit und Aufzählbarkeit
Satz: Eine Menge M, mit M\subseteq A^*, ist entscheidbar genau dann, wenn M und A^*\setminus M (Komplementmenge) aufzählbare Menge sind.
Wir wollen den Beweis des Teils "Wenn M und A^*\setminus M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge." mit einem ausführbaren Beispiel illustrieren.
Wir wählen für f die Aufzählprozedur für die ungeraden Zahlen und für g die Aufzählprozedur für die geraden Zahlen. Damit erzeugen wir die betrachteten Mengen M und A^*\setminus M.
Von beiden Mengen schauen wir uns jeweils 10 Elemente an.
Wie man sieht, haben wir es mit Mengen von Zahlwörtern zu tun.
Die Prozedure für \chi_M wurde so konstruiert, wie im Beweis angegeben. Erproben Sie selbst einige Aufrufbeispiele mit selbstgewählten Wörtern aus A^*, also Wörtern natürlicher Zahlen.