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| 350px]]

==Kreativaufgabe: RADO-Funktion==
$\sum(n)$ bezeichnet die ''maximale'' Anzahl von Einsen (nicht unbedingt aufeinander folgend), die eine haltende TM über $\{1\}^*$ und $n$ Zuständen zzgl. eines Haltezustands auf ein anfangs leeres Band schreiben kann. Die Kopfposition am Ende der Berechnung spielt (im Gegensatz zur sonstigen Vereinabrung) keine Rolle.

$\sum:\mathbb{N} \rightarrow \mathbb{N}$ ist eine von Tibor RADO (ungarischer Mathematiker, 1895-1965) angegebene ''nicht berechenbare'' Funktion.

z.z.: $\sum$ ist ''nicht berechenbar''.
Methode: Indirekter Beweis
Vorbereitung:
* Beweis der folgenden beiden Eigenschaften der Funktion:
** $\sum(n) < \sum(n+1)$
** Für alle $n$ gilt $f(n) \leq \sum(n+k)$
* Wenn $f$ und $g$ Turing-berechenbare Funktionen sind, dann ist auch $g \circ f$ Turing-berechnbar. (Beweis!)