allgemeines Halteproblem, ein Entscheidungsproblem, das bei gegebenen Zahlen n und x danach fragt, ob die Berechnung der n-ten Turing-Maschine, gestartet mit Eingabe x, irgendwann hält. Den Begriff der n-ten Turing-Maschine erhält man hierbei durch Arithmetisierung.

Das Halteproblem ist ein Beispiel für ein unentscheidbares Problem (Entscheidbarkeit), was man mit der Technik der Diagonalisierung nachweist. Das Halteproblem ist aber noch rekursiv aufzählbar bzw. semientscheidbar.

Für jedes feste n, also für jede feste Turing-Maschine, erhält man ein sog. spezielles Halteproblem, das zu gegebenem x die Frage stellt, ob diese n-te Turing-Maschine bei Eingabe x hält. Für manche Turing-Maschinen, wie die universelle Turing-Maschine, ist auch das spezielle Halteproblem unentscheidbar.

Weitere Spezialfälle des Halteproblems sind zum einen das Halteproblem bei leerem Band (gegeben n, gefragt: Hält die n-te Turingmaschine, wenn man sie auf leerem Band startet?) und das Selbstanwendbarkeitsproblem (gegeben n, gefragt: Hält die n-te Turingmaschine, wenn man sie auf der Eingabe n startet?). Beide Probleme sind unentscheidbar.