Seite 1 von 1

Frage zur Probeklausur A2 a

Verfasst: 5. Apr 2010 16:45
von Dutchie
Die Menge M1 ist doch gleich dem Problem ID?
Wenn ja, dann ist es nicht mal semi-entscheidbar( durch Diagonalisierung im Skript).
Warum ist die Menge entscheidbar und wie zeigt man das?

Danke für die Antwort schon mal.

Re: Frage zur Probeklausur A2 a

Verfasst: 6. Apr 2010 09:31
von Simon Siegler
Nein, \(ID = \{n \in \mathbb{N}\,|\, \forall i \in \mathbb{N}.\; \varphi_n(i) = i\}\), in der Aufgabe geht es aber um die Probleme \(\{n \in \mathbb{N}\,|\,\varphi_i(n) = n\}\): für jedes \(i\in\mathbb{N}\) ist das resultierende Problem semi-entscheidbar. Überlegen Sie, was \(\varphi_i\) für ein \(i\in\mathbb{N}\) überhaupt ist und wie Sie für ein \(n\in\mathbb{N}\) bestimmen können, ob \(\varphi_i(n) = n\) gilt.

Diese Probleme sind allerdings nicht für alle \(i\in\mathbb{N}\) entscheidbar.