# the problems that could exist if halting problem is solved

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