Halteproblem

Aufgabenstellung

Spielen Sie die Betrachtungen zum Halteproblem (s. Vorlesung) mit Scheme-Prozeduren nach.

Hinweis: Definieren Sie ggf. auch eine Prozedur haelt-tricky?, die \#t zurück gibt, wenn das betrachtete Programm P ein Ergebnis berechnet, und \#f, wenn die Berechnung in einer gewissen Zeit T zu keinem Ergebnis führt. Verwenden Sie zeitbeschränkte Berechnungen, deren Implementierungidee einige Kreativität erfordert.

Lösung

Beispiel-Aufruf für haelt

Beispiel-Aufruf: (haelt-tricky crazy-tricky 0)

Beweise

Aufgabenstellung

1. Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
2. Zeigen Sie, dass die Wortmenge A^\ast über A abzählbar unendlich ist.
3. Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.

Lösung

Aufgabe 1

Aufgabe 2

Die Anzahl der Wörter aus einem Alphabet A mit einer bestimmten Länge l ist endlich. Die Zahl der Wörter, die mit der Länge l aus dem Alphabet A gebildet werden können, kann mit

\begin{array}{ccc} \text{Anzahl der Elemente des Alphabets}^\text{Wortl\"ange}&=&A^l \end{array}

berechen werden.

Beispiel

Die Wortmenge A^\ast bildet sich nun aus den unendlich vielen Teilmengen A^i.

Um eine Abbildung der Wortmenge A^\ast auf die natürlichen Zahlen \mathbb{N} zu ermöglichen, ordnet man nun die einzelnen Wörter der Wortmenge nach der längenlexikografischen Ordnung. Anschließend kann jedem Wort eine natürliche Zahl zugeordnet werden.

Beispiel

{| class="wikitable"

|- ! \epsilon!! a !! b !! c !! d !! aa |- | 1 || 2 || 3 || 4 || 5 || 6 |}

Aufgabe 3

Bijektive Funktion

Aufgabenstellung

Verifzieren Sie, dass die folgende Funktion f : \mathbb{N}^+ \rightarrow \mathbb{Q}^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.

f(n)=\begin{cases} 1, &\text{wenn }n=1;\\ f(\frac{n}{2}), & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{wenn n ungerade}. \end{cases}

Lösung

(define (biject n)

 (cond
   ((or (< n 1) (not (= (round n) n))) (display "Bitte nur natürliche Zahlen eingeben!"))
   ((= n 1) 1)
   ((ist-gerade n) (+ 1 (biject (/ n 2))))
   (else (/ 1 (biject (- n 1))))))

(define (ist-gerade n)

 (cond
  ((= 1 (modulo n 2)) #f)
  (else #t)))

(define values (make-hash-table))

(define (memobiject n)

 (cond
   ((number? (hash-table-ref values n false))(hash-table-ref values n false))
   ((or (< n 1) (not (= (round n) n))) (display "Bitte nur natürliche Zahlen eingeben!"))
   ((= n 1) (hash-table-set! values 1 1))
   ((ist-gerade n) (hash-table-set! values n (+ 1 (biject (/ n 2)))))
   (else (hash-table-set! values n (/ 1 (biject (- n 1))))))
(hash-ref values n false))

Beispiel-Aufruf: (biject 5)

Beispiel-Aufruf mit Memoizing: (memobiject 1000)