BuK/IIm12/Studenten/siclsche/Thema5

Wiki-Quelltext dieser Seite.

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

'''Vorgänger''' $f:\mathbb{N} \rightarrow \mathbb{N}$

$$f(n) = \begin{cases} n-1, & \text{wenn } n \geq 1,\\
0, & \text{sonst}.
\end{cases}$$

'''Halbierung''' $f:\mathbb{N} \rightarrow \mathbb{N}$

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

$D_f = \mathbb{N}\backslash\{1234, 7266281\}$

$$f(n) = \begin{cases} n, & \text{wenn } n \ne 1234,\ n \ne 7266281,\\
\perp, & \text{sonst}
\end{cases}$$

== Aufgabe 2 ==
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.


'''Lösung für beide:'''

$$01100110100100101100110011010011010010011010010010110001001011010100100101$$

$$00100100101100110001010011010010011000100101100010010100100101001010011000100101$$

'''für x: '''

$$01 \ 10 \ 01 \ 10 \ 10 \ 01 \ 001 \ 01 \ 10 \ 01 \ 10 \ 01 \ 10 \ 10 \ 01 \ 10 \ 10 \ 01 \ 001 \ 10 \ 10 \ 01 \ 001 \ 01 \ 10$$

$$001 \ 001 \ 01 \ 10 \ 10 \ 10 \ 01 \ 001 \ 01 \ 001 \ 001 \ 001 \ 01 \ 10 \ 01 \ 10 \ 001 \ 01 \ 001 \ 10 \ 10 \ 01 \ 001 \ 10 \ 001$$

$$001 \ 01 \ 10 \ 001 \ 001 \ 01 \ 001 \ 001 \ 01 \ 001 \ 01 \ 001 \ 10 \ 001 \ 001 \ 01$$

'''für y:'''

$$011 \ 001 \ 101 \ 001 \ 001 \ 011 \ 0 \ 011 \ 001 \ 101 \ 001 \ 101 \ 001 \ 001 \ 101 \ 001 \ 001 \ 011 \ 0 \ 001 \ 001 \ 011 \ 0 \ 101 \ 001$$

$$0 \ 0 \ 101 \ 001 \ 001 \ 001 \ 011 \ 0 \ 011 \ 0 \ 0 \ 0 \ 101 \ 001 \ 101 \ 001 \ 0 \ 011 \ 0 \ 001 \ 001 \ 011 \ 0 \ 001 \ 0$$

$$0 \ 101 \ 001 \ 0 \ 0 \ 101 \ 0 \ 0 \ 101 \ 0 \ 011 \ 0 \ 001 \ 0 \ 0 \ 101$$

== Aufgabe 3==

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

1. für semi-entscheidbare Sprachen.

[[Bild:Siclsche_TM-Semientscheidbar.jpg.png]]

2. für entscheidbare Sprachen.

[[Bild:Siclsche_TM-Entscheidbar.jpg.png]]

== Aufgabe 4 ==

Entwickeln Sie eine Turing-Maschine, welche die konstante Funktion $f(x)=5$ für alle $x\in\mathbb{N}$ berechnet.

[[Bild:Siclsche_TMkonsFkt.jpg|500px]]

== Aufgabe 5 ==

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

'''Turing-aufzählbar'''

Die Menge muss abzählbar und die dazu gehörige Funktion durch eine Turing-Maschine $M$ berechenbar sein.

''' Turing-entscheidbar'''

Wenn die $\chi_M$ - Funktion durch eine Turing-Maschine berechenbar ist.

== Aufgabe 6 ==

Entwickeln Sie eine Turning-Maschine, welche den Nachfolger einer natürlichen Zahl berechnet.

[[Bild:Siclsche_TMNachfolger.jpg| 450px]]