Urza 
Grünschnabel
Dabei seit: 18.12.2007
Beiträge: 1
 |
|
| 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
|
|
