Thema5

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}

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

Aufgabe 2

Für K = ((001,0),(01,011),(01,101),(10,001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt:

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

Lösung für beide:

für x:

für y:

Aufgabe 3

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

1. für semi-entscheidbare Sprachen.

2. für entscheidbare Sprachen.

Aufgabe 4

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

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.

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 der 1. Eigenschaft: \Sigma(n) < \Sigma(n+1)

Fügt man einer bestehenden Turing-Maschine zu der RADO-Funktion mit n Zuständen einen weiteren Zustand direkt nach dem Startzustand hinzu, so ist es dieser erweiterten Turing-Maschine möglich, mindestens eine "1" mehr auf das Band zu schreiben. Dies wurde mit folgendem Beispiel für n=2 verdeutlicht. Hierbei wird über die Ausgangs-Turing-Maschine viermal "1" auf das Band geschrieben, während bei der um den Zustand q_{neu} erweiterten Turing-Maschine fünfmal "1" geschrieben wird.

Beispiel n = 2 und n = 3

Ergebnisse:

Beweis der 2. Eigenschaft: Für alle n gilt f(n) \leq \sum(n+k)

Die Funktion f(n) wird durch eine Turing-Maschine M_f berechnet. Diese besitzt k Zustände und es können mit ihr zur Berechnung von f(n) n Einsen auf das Band geschrieben werden.

Weiterhin gibt es eine Turing-Maschine zu der RADO-Funktion, die maximal viele Einsen (x) bei k Zuständen schreibt. Um mit dieser Turing-Maschine die n Einsen zur Berechnung von f(n) auf das Band zu schreiben, kommen maximal n Zustände zu der bereits bestehenden Maschine hinzu. Die so entstandene Turing-Maschine schreibt also die urspürngliche Anzahl an Einsen x und zusätzlich die n Einsen der Funktion. Somit muss die Anzahl der Einsen von \sum(n+k) mindestens n betragen.

Beweis der 3. Eigenschaft: Wenn f und g Turing-berechenbare Funktionen sind, dann ist auch g \circ f Turing-berechnbar.

Da f und g Turing-berechenbar sind, existieren für beide Funktionen Turing-Maschinen. Die Verkettung dieser beiden Funktionen kann über die Kopplung der zugehörigen Maschinen realisiert werden, sodass wieder eine Turing-berechenbare Funktion entsteht.

Beispiel:

f stellt die Turing-Maschine zur Berechnung des Nachfolgers einer natürlichen Zahl dar.

g stellt die Turing-Maschine zur Verdopplung einer natürlichen Zahl dar.

Beweis: \sum ist nicht berechenbar

Methode: indirekter Beweis \rightarrow \sum ist berechenbar

Da \sum berechenbar ist, existiert eine Turing-Maschine zu dieser Funktion. Wie in obigem Beispiel bewiesen, ist die Berechnung der Nachfolger einer natürlichen Zahl (S) ebenfalls berechenbar, sodass auch hier eine Turing-Maschine existiert. Nach Eigenschaft 3 muss die Verkettung zweier Turing-berechenbarer Funktionen ebenfalls Turing-berechenbar sein. Daraus ergibt sich:

\Sigma \circ S ist Turing-berechenbar, sodass eine Turing-Maschine M_{\Sigma \circ S} mit k Zuständen existiert. \Sigma \circ S stellt dabei eine Funktion f dar.

Nach Eigenschaft 2 gilt für alle n \in \mathbb{N} f(n) \leq \sum(n+k). f wird hierbei mit (\Sigma \circ S) ersetzt:

(\Sigma \circ S) \leq \Sigma(n+k),

wobei \Sigma \circ S auch als \Sigma(S(x)) dargestellt werden kann. Die Nachfolger-Funktion ist hierbei durch g(n) = n+1 definiert. Daraus ergibt sich:

Für ein spezielles n = k + 1 folgt folgende Gleichung:

\Sigma(k+2) \leq \Sigma(2k+1) \unicode{x021AF} Widerspruch!

Somit ist bewiesen worden, dass die RADO-Funktion nicht berechenbar ist.