Frage zur Probeklausur A2 a

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Frage zur Probeklausur A2 a

Beitrag von Dutchie » 5. Apr 2010 16:45

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.

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Frage zur Probeklausur A2 a

Beitrag von Simon Siegler » 6. Apr 2010 09:31

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.

Antworten

Zurück zu „Archiv“