Home -> Themen ->
Aufzählbarkeit
Turing-Werkstatt
Theoretische Informatik am PC
Aufzählbare Mengen
Eine Wortmenge A ist rekursiv aufzählbar, wenn es eine Turing-Maschine M gibt, die alle Worte
von A auf einem ihrer Bänder ausgibt. Dabei dürfen Worte von M auch mehrfach ausgegeben werden.

Beispiele aufzählbarer Mengen :
-
Die Menge der natürlichen Zahlen (Natuerlich.tm)
-
Die Menge aller Worte über einem beliebigen Alphabet (AlleWorte.tm)
-
Die Menge der Palindrome über einem Alphabet z.B.{a,b}
Ein Palindrom ändert sich nicht, wenn man es rückwärts liest. (Palindrome.tm)
Download aller Beispiele
Anmerkungen :
-
In Beispiel 3 ist der Zusammenhang verwendet, dass eine entscheidbare Menge A auch
aufzählbar ist. Man zählt mit AlleWorte.tm alle Worte über dem Alphabet auf und entscheidet,
ob es zu A gehört. Nur diese Worte werden ausgegeben.
-
Es gibt Mengen, die nicht aufzählbar und Mengen, die aufzählbar aber nicht entscheidbar sind.
Beispiele dafür sind das Halteproblem für Turing-Maschinen und sein Komplement.
-
Aufzählbare Mengen werden auch semi-entscheidbar genannt. Will man testen, ob ein
Wort w zur Menge A gehört, so kann man die Maschine M, die alle Worte von A
aufzählt erweitern. Immer wenn M ein neues Wort von A erzeugt hat, wird dieses
mit w verglichen. Stimmt es mit w überein, so stoppt die erweiterte Maschine M'
mit dem Ergebnis : w gehört zu A. Wenn w nicht zu A gehört gibt es allerdings
eine Endlosschleife falls A nicht endlich ist.