Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 11

Abgabe: Mittwoch, 28. Januar 2009, vor der Vorlesung Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt!

Aufgabe 1. Zeigen Sie mittels Unifikation, daß die Aussage

∃v_{1} … v_{4}(¬L(v_{1}, f(v_{1}, v_{1}), g(v_{3})) ∨ L(g(v_{3}), v_{2}, g(g(v_{4}))))

allgemeingültig ist.

Aufgabe 2. Geben Sie eine Registermaschine über dem Alphabet A = { |, ♯ } an, welche bei Eingabe eines Paares (n, m) zweier natürlicher Zahlen n und m das Produkt n · m ausgibt. Die Eingabe (n, m) soll dabei durch das Wort \underbrace{| … |}_{n mal} ♯ \underbrace{| … |}_{m mal}

kodiert sein.

Aufgabe 3. Gegeben sei eine L-Struktur A mit n Elementen. Zeigen Sie, daß A isomorph zu einer L-Struktur B ist, deren Grundmenge die Menge {1, …, n} ist.

Aufgabe 4. Wir definieren eine Funktion f : ℕ ⟶ ℕ wie folgt. Für n ∈ ℕ sei f(n) die größte endliche Schrittzahl, die ein Registerprogramm bei leerer Eingabe läuft, dessen Programmcode höchstens Länge n hat. Zeigen Sie, daß es kein Registerprogramm geben kann, welches bei Eingabe n den Wert f(n) berechnet.