Mathematische Logik/Gemischte Definitionsabfrage/3/Aufgabe/Lösung

${\displaystyle {}T=T(G)}$

${\displaystyle {}A^{*}}$

${\displaystyle {}A=V\cup K\cup \bigcup _{n\in \mathbb {N} _{+}}F_{n}}$

1. Jede Variable ${\displaystyle {}v\in V}$ ist ein Term.
2. Jede Konstante ${\displaystyle {}c\in K}$ ist ein Term.
3. Für jedes ${\displaystyle {}f\in F_{n}}$ und ${\displaystyle {}n}$ Terme ${\displaystyle {}t_{1},t_{2},\ldots ,t_{n}}$ ist auch ${\displaystyle {}ft_{1}t_{2}\ldots t_{n}}$ ein Term.

Multiplikation mit ${\displaystyle {}n}$

${\displaystyle \mu _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \mu _{n}(k),}$

für die

${\displaystyle \mu _{n}(0)=0{\text{ und }}\mu _{n}(k')=\mu _{n}(k)+n{\text{ für alle }}k\in \mathbb {N} }$

gilt.

${\displaystyle {}R_{i}}$

${\displaystyle {}B_{j}}$

1. ${\displaystyle {}i+}$ (erhöhe den Inhalt des Registers ${\displaystyle {}R_{i}}$ um ${\displaystyle {}1}$, d.h. um einen Strich).
2. ${\displaystyle {}i-}$ (reduziere den Inhalt des Registers ${\displaystyle {}R_{i}}$ um ${\displaystyle {}1}$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
3. ${\displaystyle {}C(ij)}$ (wenn das ${\displaystyle {}i}$-te Register leer ist, so gehe zum Befehl ${\displaystyle {}B_{j}}$, andernfalls zum nächsten Befehl).
4. Drucke (drucke den Inhalt des ersten Registers).
5. Halte an.

${\displaystyle \Box (\Box \alpha \rightarrow \alpha )\rightarrow \Box \alpha }$

nennt man Löb-Axiom.