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 :

1. Die Menge der natürlichen Zahlen (Natuerlich.tm)
2. Die Menge aller Worte über einem beliebigen Alphabet    (AlleWorte.tm)
3. 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.