Das Halteproblem fragt, ob ein gegebenes Programm auf einer gegebenen Eingabe anhält.
Es ist nicht entscheidbar: Es gibt keinen Algorithmus, der diese Frage für alle Programme und Eingaben korrekt beantwortet.