Berechenbarkeit #27 - Entscheidbarkeit und Unentscheidbarkeit

Wir definieren die Begriffe "entscheidbar" und "unentscheidbar" für Entscheidungsprobleme. Ein Problem ist entscheidbar, wenn es einen Algorithmus (eine DTM) gibt, der das Problem löst, indem er zu jeder Eingabe nach endlicher Zeit die richtige Antwort liefert. Tatsächlich gibt es auch Probleme, die nicht entscheidbar, also unentscheidbar sind. Ein solches Problem ist das Halteproblem.