TI1 - [Tutorium Honigbiene](https://ti1.beb.ninja)
Dieses HackMD ist Teil von [Tutorium 3](https://ti1.beb.ninja/20201121153921-tutorium_biene_3_reduktionen.html)
# Gemeinsame Lösung - Leere Taschen

**Definition**. Wir schreiben $L$ für die Menge der Gödelnummern, deren Funktionen nirgendwo definiert sind, sprich $L = \{e \in \mathbb{N} \mid \forall x: \varphi_e(x) \uparrow\}$.

**Definition.** $T = \{e \mid \forall x: \varphi_e(x) \downarrow\}$.

**Satz**. $L \le T$.

**Intuition**. Gesucht ist eine Funktion $f$, sodass $f(e)$ total ist, genau dann, wenn $e$ leer ist.

Ich möchte also jedes leere Programm in ein totales umwandeln und jedes nicht-leere in ein nicht-totales.

**Beweis**.
Sei
$$
h(e,t) = \begin{cases}
0, \text{ falls }\forall x \leq t: U'(e,x,t)=0\\
\perp, \text{sonst.}
\end{cases}
$$

$h$ ist berechenbar, weil U' berechenbar ist und beschränkte Suche berechenbar ist. Daher existiert eine Gödelnummer zu $h$. Diese nennen wir $e_h$.

Sei $f := e \mapsto s_1^1(e_h, e)$ . Diese Funktion ist wohldefiniert, da $h$ berechenbar ist und somit $\text{göd}(h)$ existiert. $f$ ist total und berechenbar, da $s^1_1$ dies ist.

Also gilt
\begin{align*}
\forall e,t: \varphi_{f(e)}(t) = \varphi_{s^1_1(e_h,e)}(t) = \varphi_{e_h}(e,t)=h(e,t).
\end{align*}

Sei $e \in \mathbb{N}$ beliebig. Nun gibt es zwei Fälle.

*Fall I:* $e \in L$. Also gilt $\forall x,t: U'(e,x,t)=0$, damit ist $h(e,t)$ für alle $t$ auch $h(e,t)=0$. Also $h(e,t) \downarrow$. Also $\varphi_{f(e)}(t)\downarrow$. Also folgt $f(e) \in T$.

*Fall II:* $e \not \in L$. Dann gibt es $x$, sodass $\varphi_e(x) \downarrow$. Es gibt also ein $t$, sodass $e$ auf $x$ in $t$ Schritten terminiert. Also $U'(e,x,t)\ne 0$. Also gibt es $t'$, sodass $h(e,t')\uparrow$. Also $\varphi_{f(e)}(t')\uparrow$. Also folgt $f(e) \not \in T$.