Home -> Themen -> Entscheidbarkeit


Turing-Werkstatt

Theoretische Informatik am PC


O-Pletsch 1862

Entscheidbare Mengen
Eine Wortmenge A ist entscheidbar, wenn es eine Turing-Maschine M gibt, die bei Eingabe eines Wortes w feststellt, ob w zu A gehört oder nicht,

Entscheidbar

Beispiele :

  1. Die Menge der Palindrome über einem Alphabet z.B. {a,b} ist entscheidbar.
    Palindrom.tm, eine Turing-Maschine mit zwei Bändern, entscheidet, ob ein Wort w ein Palindrom ist.
    Dazu kopiert die Maschine die Eingabe w in umgekehrter Reihenfolge der Buchstaben von Band1 nach Band2. Danach vergleicht sie w mit ihrem Spiegelwort. Bei Übereinstimmung ist w akzeptiert, d.h. w ist ein Palindrom.
  2. Die Menge der Primzahlen ist entscheidbar.
    Primzahl.tm ist eine Turing-Maschine mit drei Bändern, die bei Eingabe einer natürlichen Zahl n in unärer Form, d.h. als Strichzahl, entscheidet, ob n eine Primzahl ist,
    Primzahl.tm versucht die Eingabe n als Summe darzustellen n = k + k +....+ k mit 1 < k < n. Gelingt das, so ist n keine Primzahl.

Download aller Beispiele

Anmerkung :
Mit einer Menge A ist auch ihr Komplement, das sind alle Worte, die nicht zu A gehören, trivialer Weise entscheidbar.
Es ist nicht so einfach eine Menge anzugeben, die nicht entscheidbar ist. Ein solches Beispiel ist das Halteproblem für Turing-Maschinen.