What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is there

  • $\begingroup$ I think this can solve your question: cs.stackexchange.com/questions/32845/… $\endgroup$ Commented Apr 24, 2020 at 16:01
  • $\begingroup$ You appear to misunderstand the halting problem. It is not an unsolved problem in mathematics that we're striving to solve. Its unsolvability is a well-known, proven mathematical result, a property of mechanical computation, namely, the fact that there exist problems for which no mechanical computation can solve all cases. $\endgroup$ Commented Sep 22, 2020 at 6:11

1 Answer 1


"Exists" is a weird word to use here; I assume you're asking about what problems would be solvable if we were suddenly able to solve the halting problem.

Phrasing things in terms of sets of natural numbers for simplicity (as is the general approach here) you're asking for a characterization of the sets which are Turing reducible to $0'$. It turns out that this is a very robust notion. For example, the following three properties of a set $X$ are equivalent:

  • $X\le_T0'$.

  • $X$ is limit computable: there is a computable total function $f(x,s)$ such that for each $n\in\mathbb{N}$ we have $\lim_{s\rightarrow\infty}f(n,s)$ exists and is $1$ iff $n\in X$ and is $0$ otherwise.

  • $X$ is $\Delta^0_2$-definable: there are formulas $\varphi_1(z)\equiv\forall x\exists y\theta_1(x,y,z)$ and $\varphi_2(z)\equiv\forall x\exists y\theta_2(x,y,z)$ where $\theta_1,\theta_2$ use only bounded quantifiers such that $$X=\{n:\varphi_1(n)\}=\{n:\neg\varphi_2(n)\}.$$

Meanwhile, some problems which are not Turing reducible to the halting problem include:

  • Does a given Turing machine halt on all inputs?

  • Do two Turing machines accept the same language?

  • Is a given c.e. set actually computable?

The first two have Turing degree $0''$, while the third has degree $0'''$. It's worth noting that while there are sets which are not "iterations of the halting problem," and in particular there are always lots of degrees between ${\bf d}$ and ${\bf d'}$, there is strong evidence that no "natural" examples of such sets. (There's also a lot of stuff "off to the side" - for example, the set of problems which are Turing-incomparable with $0'$ has full measure and is comeager.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.