vorlesung4

Aus ProgrammingWiki
< BuK < IIm14 < Studenten < s3ankrau1
Archivierte Version vom 2015-05-10T09:52:06+00:00. Aktuelle Version

Vorlesung 4

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



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

TM semi.jpg
semi-entscheidbare Sprachen
TM entscheidbar.jpg
entscheidbare Sprachen



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.