TI1 - [Tutorium Honigbiene](https://ti1.beb.ninja)
Dieses HackMD ist Teil von [Tutorium 4](https://ti1.beb.ninja/20201126175943-tutorium_biene_4_berechenbarkeitszoo.html)
# Gemeinsame Lösung - $EQ$-Reduktion

**Definition.** Wir schreiben $EQ = \{\langle a,b \rangle \mid \varphi_a = \varphi_b\}$.

**Satz.** $EQ$ ist nicht entscheidbar.

Hier sehen wir zwei Ansätze, die nicht ganz funktionieren, und eine Lösung.

# Ansatz
**Beweis.** Wir zeigen die Aussage durch die Reduktion von $H$ auf $EQ$.

Sei $\varphi_c = x \mapsto 0$ und $\varphi_d = x \mapsto 1$. Diese gibt es, da die konstanten Funktionen berechenbar sind.

$$
h(e,x, t) = \begin{cases}
\langle c,d\rangle, &\text{falls } U'(e,x,t) = 0 \\
\langle e, e \rangle, &\text{sonst.}
\end{cases}
$$

$h$ ist berechenbar, da $U'$ total und berchenbar ist.

Sei $f:= \langle e, x \rangle \mapsto s^1_1(\text{göd}(h), e, x)$. Dann ist $f$ total und berechenbar, weil $s^1_1$ total und berechenbar und $\text{göd}(h)$ existiert.

Sei $\langle e, x\rangle$ beliebig.

*Fall 1* $\langle e,x \rangle \in H$. Also $\varphi_e(x) \downarrow$. Also gibt es ein $t \in \mathbb{N}$, sodass $U'(e,x,t) \ne 0$. Also $h(e,x,t) = \langle e,e \rangle$.

Also gilt $\varphi_{f(\langle e,x \rangle)}(t) = \langle e, e \rangle$.

Da $\langle e,e \rangle \in EQ$, gilt auch $f(\langle e,x \rangle) \in EQ$.

# Anderer Ansatz
Zu zeigen $H_e \le EQ$.

$$
f(e) = \begin{cases}
\langle e,e\rangle, &\text{falls } U(e,e) \downarrow \\
\bot, &\text{sonst.}
\end{cases}
$$

# Lösung
$H_0 \le EQ$.

Sei $\varphi_k = x \mapsto 42$. So ein $k$ existiert, weil die konstante Funktion berechenbar.

$$
h(e, x) = \begin{cases}
42, \text{falls } U(e,0) \downarrow \\
\bot, \text{sonst.}
\end{cases}
$$

$h$ ist berechenbar, weil $U$ berechenbar ist. Sei $e_h$ eine Gödelnummer zu $h$.

Sei $f : e \mapsto \langle s_1^1(e_h, e), k \rangle$. $f$ ist total und berechenbar, weil $s_1^1$ total und berchenbar ist.

Für alle $e,x$ gilt
$$
\varphi_{s_1^1(e_h,e)}(x) = \varphi_{e_h}(e,x) = h(e,x).
$$

Sei $e \in \mathbb{N}$ beliebig.
*Fall I*. $e \in H_0$. Dann gilt für alle $x$ auch $h(e,x) = 42$. Also gilt $\varphi_{s_1^1(e_h,e)}(x)=42$. Demnach gilt $\varphi_{s^1_1(e_h,e)}=\varphi_k$. Also gilt $\langle s_1^1(e_h, e), k\rangle \in EQ$.

*Fall II*. $e \not \in H_0$. Dann gilt für alle $x$ auch $h(e,x)\uparrow$. Also gilt $\varphi_{s_1^1(e_h,e)}(x)\uparrow$. Demnach gilt $\varphi_{s^1_1(e_h,e)} \ne \varphi_k$. Also gilt $\langle s_1^1(e_h, e), k\rangle \not \in EQ$.