ue5

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Mathematik vs. Informatik 1.1 Aufgabe 1 2 Postsches Korrrespondenzprobelm PCP 2.1 Aufgabe 1 2.2 Aufgabe 2 3 Turing-Maschine und Churchsche These 3.1 Turing-Maschine als Akzeptator 3.2 Turing-Aufzählbarkeit, Turing-Entscheidbarkeit

Mathematik vs. Informatik

Aufgabe 1

Defnieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Defnieren Sie außerdem eine Funktion mit $ D_f = \N \setminus \{1234, 7266281\} $.

Postsches Korrrespondenzprobelm PCP

Aufgabe 1

Für K = ((001; 0)(01; 011); (01; 101); (10; 001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt

(2 4 3 4 4 2 1 2 4 3 4 3 4 4 3 4 4 2 1 4 4 2 1 3 4 1 1 3 4 4 4 2 1 2 1 1 1 3 4 3 4 1 2 1 4 4 2 1 4 1 1 3 4 1 1 3 1 1 3 1 2 1 4 1 1 3)

Uberprüfen Sie die angegebene Lösung per Hand.

Lösung siehe Bild...

Aufgabe 2

Entwickeln Sie eine Scheme-Prozedur (ProgrammingWiki), die bei Aufruf für eine gegebene Instanz eine Lösung des PCP findet, falls eine solche existiert und der Rechenaufwand im Rahmen bleibt.

(define erstelle-zeile (lambda (ill len) (letrec ( (helper (lambda (liste len) (if (> len 0) (append (helper liste (- len 1)) (list (append liste (list len)))) '() ) ) )) (if (null? ill) '() (append (list (car ill)) (helper (car ill) len) (erstelle-zeile (cdr ill) len)) ) ) ) ) (define erstelle-ill (lambda (len depth) (letrec ( (erstelle-initialliste (lambda (len) (if (> len 0) (append (erstelle-initialliste (- len 1)) (list (list len))) '() ) ) ) (helper (lambda (depth ill) (if (> depth 0) (erstelle-zeile (helper (- depth 1) ill) len) (erstelle-zeile (erstelle-initialliste len) len) ) ) )) (helper depth '()) ) ) ) (define get-item (lambda (liste index) (letrec ((helper (lambda (rl current-index) (cond ((= current-index index) (car rl)) ((null? rl) null) (else (helper (cdr rl) (+ current-index 1))) ) ) )) (helper liste 1) ) ) ) (define pcp (lambda (pairs depth) (letrec ((erzeuge-wort (lambda (fn il) (if (null? il) "" (string-append (fn (get-item pairs (car il))) (erzeuge-wort fn (cdr il))) ) )) (helper (lambda (reduced-ill) (if (null? reduced-ill) #f (if (string=? (erzeuge-wort car (car reduced-ill)) (erzeuge-wort cadr (car reduced-ill))) (car reduced-ill) (helper (cdr reduced-ill)) ) ) ))) (helper (erstelle-ill (length pairs) depth)) ) ) )

(pcp '(("1" "101") ("10" "00") ("011" "11")) 2)

ausführen

Turing-Maschine und Churchsche These

Turing-Maschine als Akzeptator

Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:

• für semi-entscheidbare Sprachen
• für entscheidbare Sprachen

Turing-Aufzählbarkeit, Turing-Entscheidbarkeit

Definierten Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.