Entscheidbarkeit
-
Ist ein Problem entscheidbar, wenn es eine Turingmaschine für dieses Problem gibt?
-
Kommt darauf an, was du mit "es gibt eine Turingmaschine dafür" meinst.
Wenn du eine TM hast, die für jede Eingabe anhält (und JA oder NEIN) ausgibt, dann ist das Problem entscheidbar. Es existieren aber auch Probleme, bei denen kannst du in nur eine JA-Antwort mit Sicherheit erhalten (z.B. das Halteproblem) - die sind nicht entscheidbar, sondern nur aufzählbar.
-
wie kann ein problem aufzählbar sein? Kann man sagen, dass ein Problem entscheidbar ist, wenn es auf jede Fragestellung eine JA oder NEIN Antwort gibt?
-
Erstmal: Ein "Problem" ist eine Menge von Zeichenketten (mit einem vorgegebenen Zeichenvorrat) und eine Teilmenge der Menge aller möglichen Zeichenketten.
Entscheidbar bedeutet: Du kannst in endlicher Zeit sagen, ob eine gegebene Zeichenkette in der Menge enthalten ist oder nicht (z.B. die Menge aller Primzahlen oder die Menge aller syntaktisch korrekten C-Programme).
Aufzählbar bedeutet: Du kannst sicher sagen, ob die Zeichenkette in der Menge ist - aber du kannst nicht beweisen, wenn sie nicht in der Menge ist (z.B. die Menge aller C-Programme, die garantiert anhalten).
(die Bezeichnung kommt daher, daß man in der Lage ist, per trial-and-error alle Elemente der Menge aufzuzählen)
-
Verstehe. Und eine Funktion ist nicht berechenbar, wenn ein Algorithmus sie in nicht endlicher Zeit lösen kann?
-
ratzen schrieb:
wenn ein Algorithmus sie in nicht endlicher Zeit lösen kann
Besser: Wenn kein Algorithmus sie in endlicher Zeit loesen kann.