Übungen zur Theoretischen Informatik Blatt 6 1) (a) Wie sieht die charakteristische Funktion der Teilmengen {1,3} und {2,3,5} von {1,2,3,4,5} aus? (b) Zeigen Sie, dass es eine Bijektion zwischen den Teilmengen einer n -elementigen Menge und den {0,1}-Folgen der Länge n gibt. Lösung: Die charakteristische Funktion einer Teilmenge T ⊆ A ist wie folgt deniert: χ(T ) = {x1 ..xn : xi = 1 ⇔ i ∈ T } Für die Mengen {1,3} und {2,3,5} sieht die Funktion folgendermaÿen aus: χ({1, 3}) = 10100 χ({2, 3, 5}) = 01101 Die charakteristische Funktion χ ordnet jeder Teilmenge T ⊆ A einen Bitstring der Länge n zu. Es bleibt also zu zeigen, dass für jeden Bitstring der Länge n genau eine Teilmenge gefunden werden kann. Dazu werden die Elemente der Menge A nummeriert. Die neue Funktion χ−1 sieht wie folgt aus: χ−1 (x1 ..xn ) = {i : xi = 1} 2) (a) Zeigen Sie, dass die Menge der Primzahlen in N entscheidbar ist. (b) Zeigen Sie, dass die Menge der Quadratzahlen in N entscheidbar ist. Lösung: Zu zeigen ist, dass es ein Verfahren gibt, welches entscheidet, ob ein Element x zur Menge A gehört oder nicht. Dies geschieht durch Angabe des Verfahrens. Sei x ∈ N . Um zu zeigen, dass x eine Primzahl ist, muss man feststellen, dass x nur 1 und sich selbst als Teiler besitzt. Dies erreicht man, indem man für sämtliche Zahlen y < x einen Rest bei der Division erhält. Um zu zeigen, dass x eine Quadratzahl ist, muss die Wurzel aus x eine ganze Zahl sein. Auch hier kann man sämtliche Zahlen durchgehen und probieren. 3) Zeigen Sie, dass die Menge der Turing-Maschinen {Tu : Tu hält bei Eingabe u, u ∈ N } semi-entscheidbar ist. Lösung: Semi-Entscheidbarkeit besteht darin, dass man nur genau sagen kann, ob ein Element x zur Menge A gehört. Über den Fall, dass x nicht zu A gehört, wird keine Aussage getroen. Sei also Tu eine Turingmaschine. Wir haben gelernt, dass eine Turingmaschine durch ihr Programm repräsentiert wird; daher sei u die Codierung des Programms. Die Frage ist, ob Tu bei der Eingabe u irgendwann hält. Das kann man am einfachsten überprüfen, indem man das Programm startet. Nun kann es sein, dass Tu recht bald in einem denierten Endzustand anhält. In diesem Fall ist die Entscheidung recht einfach. Die Berechnung kann aber auch etwas länger dauern, so dass die Turingmaschine in den nächsten Tagen nicht 1 hält. Man könnte nun als voreiligen Schluss ziehen, dass die Maschine bei dieser Eingabe nicht hält. Was aber falsch ist, denn irgendwann wird die Maschine halten. Im dritten und letzten Fall wird die Maschine nicht halten. Man kann also beliebig lange warten, aber schlieÿlich immer noch nicht sagen können, ob die Maschine noch hält oder nicht. Halten wir fest: Wenn die Maschine irgendwann hält, dann werden wir dies feststellen und können diese Maschine der Menge hinzufügen. Hält die Maschine allerdings nicht, so können wir keine Aussage machen - sie könnte ja noch irgendwann halten. 4) Zeigen Sie unter Zuhilfenahme der Funktionen c, e, f aus der letzten Übung, dass eine Menge genau dann rekursiv aufzählbar ist, wenn sie semi-entscheidbar ist. Lösung: Angenommen, A sei rekursiv aufzählbar mit der Funktion f. Dann können wir ein Semi-Entscheidungsverfahren für A angeben: Input(x) for n := 0, 1... do if f (n) = x then output(1) end; end Nehmen wir nun an, A 6= ∅ sei semi-entscheidbar. Wir müssen eine totale und berechenbare Funktion angeben, die A als Wertebereich besitzt: Input(n) Interpretiere n als Codierung eines Paares von natürlichen Zahlen, z.B. n = c(x, y). Seien x und y die zugeordneten Zahlen, also x = e(n) und y = f (n) (falls kein zugehöriges Paar gefunden werden kann, so setze x = 0 und y = 0. if M akzeptiert x in y Schritten then output(x) else output(a) end 2