Home -> Themen -> Aufzählbarkeit


Turing-Werkstatt

Theoretische Informatik am PC


Borsig

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.

aufzählbar

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 :