One post tagged with "automata theory"

Die Standardnummerierung ist festgelegt als:

• $\mathbb{N}_0$: Die Menge aller Turingmaschinen (ein $i \in \mathbb{N}_0$ repräsentiert die Gödelnummer einer Turingmaschine), wobei $\mathcal{T}$ die Menge aller normierten Turingmaschinen ist. Die Abbildung $h: \mathbb{N}_0 \rightarrow \mathcal{T}$ ist definiert durch $h(i) = \begin{cases} T, & \text{falls } p(\tau(T)) = i\\ T_{\omega}, & \text{sonst} \end{cases}$ bildet also auf eine natürliche Zahl eine Turingmaschine ab.
• $\mathcal{P}$: Die Menge aller berechenbaren Funktionen.
• $\varphi: \mathbb{N}_0 \rightarrow \mathcal{P}$ ist eine Abzählung aller berechenbaren Funktionen. $\varphi$ ist festgelegt durch $\varphi(i) = f \Leftrightarrow f_{h(i)} = f$ Die berechenbare Funktion $\varphi(i)$ wird also durch die $i$-te Turingmaschine berechnet.

Die Standardnummerierung ist im Folgenden die Grundlage für die Formulierung von Entscheidbarkeitsproblemen bei Mengen.

Das spezielle Halteproblem​

Zunächst wird das spezielle Halteproblem (auch Selbstanwendbarkeitsproblem) betrachtet.
Vossen und Witt definieren es über folgende Menge:

$K$ enthält alle Nummern von Turingmaschinen, die, angewendet auf sich selbst, anhalten:

• $i$ ist die Codierung einer Turingmaschine.
• $\varphi_i$ ist die berechenbare Funktion, die von der Turingmaschine $p(\tau(T)) = i$ berechnet wird.
• $\text{Def}(\varphi_i)$ ist der Definitionsbereich der Funktion $\varphi_i$, also alle erlaubten Eingaben.
• $i \in \text{Def}(\varphi_i)$ bedeutet: Die Codierung $i$ der Turingmaschine $p(\tau(T)) = i$, die $\varphi_i$ berechnet, ist eine erlaubte Eingabe.

Vossen und Witt definieren $K$ als die "Menge aller Turingmaschinen, die, [...] anhalten."
Das bedeutet, dass von einer entscheidbaren Menge ausgegangen wird:
Es wird angenommen, dass sowohl $K$ als auch $\overline{K}$ semi-entscheidbar sind und die charakteristische Funktion $\chi_K$ von $K$ berechenbar ist.

Mit Satz 10.7 formulieren Vossen und Witt den Kern des Selbstanwendbarkeitsproblems, nämlich, dass $K$ zwar semi-entscheidbar, aber nicht entscheidbar ist:

Damit wird behauptet:

• $K$ ist semi-entscheidbar, da rekursiv-aufzählbar.
  Wenn $K$ semi-entscheidbar ist, ist auch die semi-charakteristische Funktion von $K$, $\chi'_K$, berechenbar.
  Wenn $K$ semi-entscheidbar und damit rekursiv aufzählbar ist, dann gilt äquivalent dazu: $K$ ist der Definitionsbereich einer berechenbaren Funktion $g: \mathbb{N}_{0} \rightarrow \mathbb{N}_0$ (s. Folgerung 10.2 [📖VW16, p. 356]). Es reicht also aus, eine solche Funktion anzugeben, um die Semi-Entscheidbarkeit und damit auch die rekursive Aufzählbarkeit nachzuweisen.
• Wenn $K$ entscheidbar ist, dann ist auch die charakteristische Funktion $\chi_K$ berechenbar: $\chi_K$ gibt $1$ aus, wenn die Turingmaschine $T$ angewendet auf $i = p(\tau(T))$ anhält (also wenn $\varphi_i(i)$ berechnet wird); und ansonsten ist $\chi_K(i) = 0$, wenn $T$ nicht anhält².

Beweisführung​

Der Beweis wird wie folgt geführt:

a) Vossen und Witt definieren die Funktion $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ durch

Bei $u_{\varphi}$ handelt es sich um die universelle Funktion von $(\mathbb{N}_0, \mathcal{P}, \varphi)$:

$u_{\varphi}(i, j)$ berechnet die $i$-te berechenbare Funktion für die Eingabe $j$.

Mit $f$ als berechenbare Funktion kann gezeigt werden:

womit $K = \text{Def}(f)$ ist und damit $K$ rekursiv-aufzählbar und semi-entscheidbar ist.

b) Angenommen, $K$ ist entscheidbar. Dann ist $\chi_K$ berechenbar.
Vossen und Witt definieren eine berechenbare (Hilfs-)Funktion

$g: \mathbb{N}_0 \rightarrow \mathbb{N}_0$

durch

$g$ ist total berechenbar: Wenn $\chi_K(x) = 1$, dann ist $x \in \text{Def}(\varphi_x)$, und damit ist $u_\varphi(x, x) + 1 = \varphi_x(x) + 1$.

Da $g$ total berechenbar ist ($g \in \mathcal{R} \subset \mathcal{P}$), muss es ein $p \in \mathbb{N}_0$ geben mit $g = \varphi_p$. Es folgt

Für $g(p)$ werden nun zwei Fälle untersucht:

• Fall 1: $g(p) = 0$

  $$\begin{align} g(p) = 0 &\Leftrightarrow \chi_K(p) = 0 \quad \text{(Entscheidbarkeit $K$)}\\ & \Leftrightarrow p \notin K \\ & \Leftrightarrow p \notin \text{Def}(\varphi_p) \quad \text{($g = \varphi_p$)}\\ & \Leftrightarrow p \notin \text{Def}(g) \\ & \Leftrightarrow g(p) = \bot \quad \text{(Widerspruch zu $g$ total berechenbar)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = 0 \Leftrightarrow g(p) = \bot$$

• Fall 2: $g(p) = u_{\varphi}(p,p) + 1$

  $$\begin{align} g(p) &= u_{\varphi}(p, p) + 1 \quad \text{(Definition $g$)}\\ &= \varphi_p(p) + 1 \quad \text{($u_{\varphi}(p, p) = \varphi_p(p)$)}\\ &= g(p) + 1 \quad \text{($\varphi_p = g$)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = g(p) + 1$$

Insgesamt wird durch den Beweis gezeigt: Die Anwendung von $g$ auf $p$ - also von $g$ auf sich selbst (wegen $g = \varphi_p = f_{h(p)}, \varphi_p(p) = u_{\varphi}(p, p)$) - führt in jedem Fall zu einem Widerspruch.
Damit ist gezeigt, dass $\chi_K$ nicht berechenbar und folglich $K$ nicht entscheidbar ist.