Beispiel einer aufzählbaren aber nicht entscheidbaren Menge |
18.12.2007, 00:55 | Auf diesen Beitrag antworten » |
Urza | 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 |
|
|
18.12.2007, 11:57 | Auf diesen Beitrag antworten » |
Tobias | http://www.matheboard.de/thread.php?postid=629120#post629120 |
|