Informatiker Board | Druckvorschau: Beispiel einer aufzählbaren aber nicht entscheidbaren Menge

Geschrieben von Urza am 18.12.2007 um 00:55:

Beispiel einer aufzählbaren aber nicht entscheidbaren Menge

Hallo,

Sei A ein endliches Alphabet (Menge von Zeichen) und A* die Menge der Zeichenketten aus Zeichen in A.
Ich suche für irgendein konkretes A (z.B. A={'1'}, A*=IN sozusagen) eine Teilmenge M von A, sodass M aufzählbar, aber nicht entscheidbar ist.
D.h. es soll einen Algorithmus geben, der nacheinander alle Elemente von M aufzählt, aber es soll keinen Algorithmus geben, der als Eingabe ein beliebiges Element von A* nimmt und als Ausgabe "ja" oder "nein" liefert, je nach dem, ob die Eingabezeichenkette in M liegt oder nicht (und der immer nach endlicher Zeit fertig wird).
Ich bin mir im Moment garnicht sicher, ob es sowas überhaupt geben kann (für mich ist das Gebiet "Berechenbarkeitstheorie" Neuland!)

Gruß,
Urza