Beispiel einer aufzählbaren aber nicht entscheidbaren Menge

Neue Frage »

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
 
Auf diesen Beitrag antworten »
Tobias

http://www.matheboard.de/thread.php?postid=629120#post629120
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »