Mathematische Logik/Gemischte Satzabfrage/17/Aufgabe/Lösung

Es sei ${}\Gamma$ eine Menge an ${}S$ -Ausdrücken (über einem Symbolalphabet ${}S$ ), die maximal widerspruchsfrei ist und Beispiele enthält. Dann ist die durch die kanonische Termidentifizierung gegebene Interpretation ein Modell für ${}\Gamma$ .
Die Menge
${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

ist nicht
${}R$ -entscheidbar.
Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht ${}R$ -entscheidbar.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.