structural:scholar_edition
Generalization

Many variants of the halting problem can be found in computability textbooks. Typically, these problems are RE-complete and describe sets of complexity Σ 1 0 {\displaystyle \Sigma _{1}^{0}} in the arithmetical hierarchy, the same as the standard halting problem. The variants are thus undecidable, and the standard halting problem reduces to each variant and vice-versa. However, some variants have a higher degree of unsolvability and cannot be reduced to the standard halting problem. The next two examples are common.