Widerspruchsfreie entscheidbare Ausdrucksmenge/Repräsentierbare Relationen und Funktionen sind entscheidbar bzw. berechenbar/Aufgabe

Es sei ${}\Gamma \subseteq L^{\rm {ar}}$ eine widerspruchsfreie und ${}R$-entscheidbare Ausdrucksmenge.

a) Zeige, dass jede in ${}\Gamma$ repräsentierbare Relation ${}R\subseteq \mathbb {N} ^{r}$ ${}R$-entscheidbar ist.

b) Zeige, dass jede in ${}\Gamma$ repräsentierbare Abbildung

$\varphi \colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

${}R$-berechenbar ist.

Eine Lösung erstellen