Allgemeines Halteproblem (H)

Das allgemeine Halteproblem $H$ fragt, ob eine Turing-Maschine $M_{w}$ auf einer spezifischen Eingabe $x$ anhält.

H := {w # x ∣ M_{w} hält auf Eingabe x}

Eigenschaft: $H$ ist unentscheidbar (folgt aus $K \leq H$ )