Prinzipielle Grenzen der Berechenbarkeit

Abzählbarkeit

Merke Eine Menge $M$ nennt man abzählbar, wenn sie entweder leer ist ($M=\emptyset$) oder es eine Funktion $f: \mathbb{N}\rightarrow M$ gibt, die surjektiv ist (jedes Element aus $M$ ist das Bild von mindestens einer natürlichen Zahl). Etwas anschaulicher ist die Vorstellung, dass die Menge $M$ höchstens genauso viele Elemente haben darf, wie die natürlichen Zahlen.

Beispiele für abzählbare Mengen:

• die Menge der natürlichen Zahlen $\mathbb{N}=\{1,2,3,4,5,6,\ldots\}$
• die Primzahlen $\{2,3,5,7,11,13,17,19,23,\ldots\}$
• die Menge der ganzen Zahlen $\mathbb{Z}=\{0,1,-1,2,-2,3,-3,\ldots\}$
• jede Menge mit endlich vielen Elementen
• die Menge der rationalen Zahlen $\mathbb{Q}=\left\{\frac{p}{q}\mbox{ mit }p\in\mathbb{Z},q\in\mathbb{N}\right\}$ (= die Menge aller Brüche)

Beispiele für nicht abzählbare Mengen:

• die Menge der reellen Zahlen $\mathbb{R}$
• die Potenzmenge der natürlichen Zahlen $\mathbb{P}(\mathbb{N})$, also die Menge aller Teilmengen der natürlichen Zahlen

Programme sind eine endliche Folge von Wörtern über einem endlichen Alphabet (in der Praxis meist der ASCII-Code). Schreibt man den kompletten Programmtext in eine Zeile, so kann man die einzelnen Programme zunächst der Länge nach ordnen. Innerhalb der Programme einer festen Länge ordnet man diese lexikographisch, d.h. wie in einem Telefonbuch. Damit kann man folgern, dass die Menge der Programme abzählbar ist.

Gödelisierung

Wir versuchen jetzt Hilfe von der Mathematik zu erhalten. Dazu wandelt man Probleme in eine Form um, die es erlaubt, Wissen über Abbildungen innerhalb der natürlichen Zahlen zu benutzen. Um dies zu erreichen, wandelt man die Ein- und Ausgabedaten in natürliche Zahlen um. Dies kann mehr oder minder geschickt erfolgen. Kurt Gödel hat sich mit solchen Fragestellungen beschäftigt, weshalb man entsprechende Verfahren Gödelisierungen nennt..

Aufgabe   Die 26 Buchstaben des Alphabets werden mit den Zahlen 1 bis 26 kodiert. Damit könnte man ein geschriebenes Wort als Zahl schreiben. Dekodiere die Zahl "26235945212097"! Welche Buchstabenfolge erhält man nach dem Dekodieren? [Lösung anzeigen][Lösung ausblenden] Möglichkeiten für das dekodierte Wort sind z.B.: ZWEIDEUTIG oder BFBCEIDEBATIG oder ...

Aufgabe   Nun werden die 26 Buchstaben des Alphabets wie folgt kodiert: Den 26 Buchstaben des Alphabets wird jeweils eine eindeutige Zahl zwischen 1 und 26 zugeordnet. Ein Wort wird nun mit fortlaufenden Primzahlpotenzen kodiert, also wenn a die Zahl 1, b die Zahl 2, c die Zahl 3 zugeordnet wird, dann wird das Wort abbca wie folgt kodiert: a ist der erste Buchstabe des Wortes und 2 die erste Primzahl. Also wird das a mit $2^1=2$ kodiert. b ist der zweite Buchstabe des Wortes und 3 die zweite Primzahl. Also wird das b mit $3^2=9$ kodiert. b ist der dritte Buchstabe des Wortes und 5 die dritte Primzahl. Also wird dieses b mit $5^2=25$ kodiert. c ist der vierte Buchstabe des Wortes und 7 die vierte Primzahl. Also wird das c mit $7^3=343$ kodiert. a ist der fünfte Buchstabe des Wortes und 11 die fünfte Primzahl. Also wird dieses a mit $11^1=11$ kodiert. Multipliziert man diese Zahlen miteinander, erhält man die Zahl $2\cdot 9\cdot 25\cdot 343\cdot 11=1697850$. Da die Primfaktorzerlegung eindeutig ist, wenn man die Primzahlpotenzen aufsteigend ordnet, kann man aus jeder Zahl das zugehörige Wort erzeugen. Welche Buchstabenfolge erhält man, wenn man die Zahl $2^9\cdot 3^{14}\cdot 5^6\cdot 7^{15}\cdot 11^{18}\cdot 13^{13}\cdot 17^{1}\cdot 19^{20}\cdot 23^9\cdot 29^{11}$dekodiert? [Lösung anzeigen][Lösung ausblenden] Das dekodierte Wort lautet: INFORMATIK. Dies Art der Kodierung ist eher von theoretischer Bedeutung, weil man sehr schnell gigantisch große Zahlen erhält. Es ist auch ziemlich aufwändig diese Zahlen in Primfaktoren zu zerlegen. Aus diesem Grund sind große Primzahlen für die Verschlüsselungstechnik so wichtig.

Aufgabe   Nun werden die 26 Buchstaben des Alphabets mit den Zahlen 01 bis 26 kodiert. Schreibt man die kodierten Buchstaben hintereinander, so erhält man eine Zahl. Dekodiere die Zahl 26230509060512121519. [Lösung anzeigen][Lösung ausblenden] Das dekodierte Wort lautet: ZWEIFELLOS

Mit der Gödelisierung lassen sich beliebige Eingabedaten in natürliche Zahlen umwandeln. Diese Vorgehensweise wird häufig in der theoretischen Informatik verwendet, da sich Algorithmen dadurch auf Funktionen über den natürlichen Zahlen abbilden lassen. Dafür gibt es verschiedenste Verfahren. Man fasst solch ein Verfahren als Abbildung $g$ von der Menge der Programme $M$ in die Menge der natürlichen Zahlen $\mathbb{N}$ auf: $g: M \rightarrow \mathbb{N}$. Die Abbildung muss dabei noch drei Bedingungen erfüllen:

• $g$ muss injektiv sein, d.h. jede natürliche Zahl darf höchstens das Bild von einem Programm sein; aber nicht jede natürliche Zahl muss auch ein Programm sein
• Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt.
• Die Umkehrfunktion $g^{-1}$ muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können.

Welches der obigen Verfahren eignet sich für eine Gödelisierung? (!Kodierung mit Zahlen 1 bis 26) (Kodierung mit Zahlen 01 bis 26) (Kodierung mit Primzahlpotenzen)(!Keines der Verfahren)

Halte-Problem

Aufgabe   Die Schüler der Kollegstufe besuchen $n$ verschiedene Kurse. Jeder Kurs findet einmal pro Woche statt. Belegt ein Schüler zwei Kurse, so dürfen diese nicht gleichzeitig stattfinden. Kann man mit $k$ verschiedenen Terminen auskommen? Erstelle hierzu eine Graphen, wobei ein Knoten einem Kurs entspricht. Zwei Knoten werden genau dann miteinander verbunden, wenn ein Schüler die beiden entsprechenden Kurse besucht. Man kann die Aufgabe als sogenanntes k-Farbproblem auffassen.