BuK/IIm14/Studenten/s3ankrau1/vorlesung4

Wiki-Quelltext dieser Seite.

'''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:

[[Datei:TM semi.jpg|200px]]

* entscheidbare Sprachen:

[[Datei:TM entscheidbar.jpg|200px]]


----


'''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.