Mathematisches Institut

Mengenlehre & Logik II

Sommersemester 2001 Benedikt Löwe

Blatt 10 Abgabetermin: 5. Juli 2001

Aufgabe 47

Geben Sie eine Turingmaschine an, die exakt bei den geraden Inputs (also bei den Inputs ⟨00000 …⟩, ⟨11000 …⟩, ⟨11110 …⟩, usw.) hält und sonst in eine Endlosschleife läuft.

Aufgabe 48

Seien x und y berechenbare reelle Zahlen, also Funktionen von ω nach ω. Zeigen Sie, daß dann auch die Zahl x ∘ y : n ↦ x(y(n)) berechenbar ist.

Aufgabe 49 Wir definieren eine etwas mächtigere Turingmaschinenarchitektur: Sei S eine Zustandsmenge wie in (13.2). Wir wollen eine Funktion p : S × 2 →

S × (2 × ω) × 2 ein schnelles Programm nennen. Wenn p(q, b) = ⟨q^{∗}, ⟨b_{0}, v⟩, b_{1}⟩ ist, dann soll die zusätzliche Information n angeben, um wieviele Schritte die Maschine nach links (falls b_{0} = 0) oder nach rechts (falls b_{0} = 1) geht.

In der Beschreibung der Berechnungsfolge (vgl. (13.5)) verändert sich lediglich die Definition von h:

h(n + 1) : \{ \begin{matrix}h(n) + v & b_{0} = 1, \\ max\{0, h(n) − v\} & b_{0} = 0. \end{matrix}

Wir wollen ⟨S, p⟩ eine Schnellmaschine nennen, falls S eine Zustandsmenge und p ein schnelles Programm ist. Eine reelle Zahl heiße schnell berechenbar falls eine Schnellmaschine existiert, die bei jedem Sequenzenstring der Dimension 1 hält und einen Sequenzenstring der Dimension 1 ausgibt.

Zeigen Sie, daß eine Zahl genau dann schnell berechenbar ist wenn sie berechenbar ist.

Aufgabe 50 Betrachten Sie das folgende “Schema der primitiven Rekursion”: Sei F eine Klasse von Funktionen. Wir sagen, F sei abgeschlossen unter primi-

tiver Rekursion falls für je zwei Funktionen g_{0}, g_{1} ∈ F auch die durch die folgenden Rekursionsgleichungen definierte Funktion f in F ist:

f(a, 0) := g_{0}(a),
f(a, b + 1) := g_{1}(a, f(a, b)).

(1) Zeigen Sie, dass die Klasse der berechenbaren Funktionen unter primitiver Rekursion abgeschlossen ist.

(2) Zeigen Sie, dass die Exponentialfunktion ⟨n, m⟩ ↦ n^{m} berechenbar ist.

(Bitte zeigen Sie dies nicht durch explizite Angabe der Turingmaschinen, sondern beschreiben Sie mit Wort und Bild, was die Turingmaschinen tun sollen.)

Aufgabe 51

Zeigen Sie: Jede partiell berechenbare Funktion f : ω^{n} → ω^{m} ist rekursiv aufzählbar als Teilmenge von ω^{n+m}.