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


"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.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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