vorlesung4

Aus ProgrammingWiki
< BuK < IIm14 < Studenten < s3ankrau1

Definieren Sie je eine totale Funktion fur den Vorgänger und die Halbierung einer natürlichen Zahl. Definieren Sie außerdem eine Funktion mit D_f = \N \backslash \{1234, 7266281\}.

  • (a) Vorgänger der natürlichen Zahl:
f(n) = \left\{ \begin{array}{l l} n-1 & \quad \text{wenn } n>0\\ 0 & \quad \text{sonst} \end{array} \right.
  • (b) Halbierung einer natürlichen Zahl:
f(n) = \left\{ \begin{array}{l l} \frac{n}{2} & \quad \text{wenn } n|2\\ \frac{n+1}{2} & \quad \text{sonst} \end{array} \right.
  • (c) D_f = \N \backslash \{1234, 7266281\}:
f(n) = \left\{ \begin{array}{l l} n & \quad \text{wenn } n \neq 1234, 7266281\\ \perp & \quad \text{sonst} \end{array} \right.



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)

Überprüfen Sie die angegebene Lösung per Hand.

X = 0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101

Y = 0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101



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



Geben Sie Trichterbilder fur den Einsatz einer TM als Akzeptor an:

  • semi entscheidbare Sprachen:

TM semi.jpg

  • entscheidbare Sprachen:

TM entscheidbar.jpg



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

Sei A ein Alphabet, M \subseteq A^*. M heißt Turing-entscheidbar, falls die charakteristische Funktion \chi_M Turing-berechenbar ist.

M heißt Turing-aufzählbar, wenn es eine Funktion f : \N \rightarrow M gibt, die surjektiv und Turing-berechenbar ist.