Foundations of Unsolvability: Hierarchy and Priority in Recursion Theory

The study of recursion theory is an investigation into the algorithmic limits of mathematics. By mapping the hierarchy of unsolvability, we delineate the boundary between the effectively calculable and that which necessitates transfinite complexity. This paper addresses three core pillars of this field: the diagonalizing nature of the Halting Problem, the structural classification of sets within the arithmetical hierarchy, and the construction of Turing-incomplete recursively enumerable (r.e.) sets via finite injury priority arguments.

I. Diagonalization and the Halting Problem

The Halting Set $K=\{e\mid {\varphi }_e(e)\downarrow \}$ is the foundational set that is r.e. but not recursive.

Proof of Recursive Enumerability: Let $W_e$ be the domain of the $e$-th partial computable function ${\varphi }_e$. By definition, $K=\{e\mid e\in W_e\}$. Since the universal function $\psi (e,x)={\varphi }_e(x)$ is computable, $K$ is r.e..

Proof of Non-Recursiveness: Suppose $K$ were recursive. Then its characteristic function ${\chi }_K$ would be total computable. We define a partial computable function $f(x)$ as follows: $f(x)=\{\begin{array}{ll}\uparrow & \text{if }x\in K\\ 0& \text{if }x\notin K\end{array}$ Since $f$ is partial computable, by the Indexing Theorem (or Kleene’s Normal Form), there exists an index $k$ such that $f={\varphi }_k$. Consider the value $f(k)$:

• If $k\in K$, then by definition of $K$, ${\varphi }_k(k)\downarrow$. But by our definition of $f$, if $k\in K$, $f(k)\uparrow$. This is a contradiction.

• If $k\notin K$, then by definition of $K$, ${\varphi }_k(k)\uparrow$. But by our definition of $f$, if $k\notin K$, $f(k)=0$. This is a contradiction. Thus, $K$ cannot be recursive.

Significance: The Halting Problem demonstrates that there are well-defined mathematical problems for which no algorithm exists. This establishes that computational limits are intrinsic to formal systems, rather than limitations of physical hardware.

II. Reductions and the Arithmetical Hierarchy

The classification of sets into ${\Sigma }_n^0$ and ${\Pi }_n^0$ levels provides a structural scaffold for computational complexity. A set $A\in {\Sigma }_n^0$ if it is definable by a formula with $n$ alternating quantifiers starting with $\exists$ over a recursive predicate.

Post’s Theorem: A set $A$ is ${\Delta }_{n+1}^0$ (where ${\Delta }_{n+1}^0={\Sigma }_{n+1}^0\cap {\Pi }_{n+1}^0$) if and only if $A$ is computable in a set that is ${\Sigma }_n^0$. More broadly, ${\Sigma }_{n+1}^0$ sets are exactly those r.e. in ${\varnothing }^{(n)}$ (the $n$-th jump of the empty set). This connects the logical complexity of set definitions to their computational information content.

Totality and ${\Pi }_2^0$-Completeness: Let $Tot=\{e\mid {\varphi }_e\text{ is total}\}$. $Tot\in {\Pi }_2^0$ because $e\in Tot⟺\forall x\exists sT(e,x,s)$, where $T$ is Kleene’s $T$-predicate. To show ${\Pi }_2^0$-completeness, let $S$ be any ${\Pi }_2^0$ set: $x\in S⟺\forall y\exists zP(x,y,z)$. By the $s-m-n$ theorem, there exists a total computable function $f$ such that ${\varphi }_{f(x)}(y)$ searches for a $z$ satisfying $P(x,y,z)$. If the search succeeds, ${\varphi }_{f(x)}(y)\downarrow$; if not, it diverges. Thus, $x\in S⟺{\varphi }_{f(x)}$ is total. This uniform reduction places $Tot$ strictly higher than the Halting Problem, demonstrating that ${\Pi }_2^0$ represents a higher level of computational "hardness".

III. The Friedberg-Muchnik Theorem

The Friedberg-Muchnik Theorem solves Post’s Problem by constructing two r.e. sets $A$ and $B$ such that $A/{\le }_{T}B$ and $B/{\le }_{T}A$.

Construction: We define requirements $R_{2e}:{\Phi }_e^B\ne A$ and $R_{2e+1}:{\Phi }_e^A\ne B$. To satisfy $R_{2e}$, we choose a witness $x_e$, wait for a stage $s$ such that ${\Phi }_{e,s}^{B_s}(x_e)\downarrow =0$, and enumerate $x_e$ into $A$. To ensure this disagreement persists, we must prevent future changes to $B$ on the usage of the computation ${\Phi }_e^{B_s}(x_e)$. We define a restraint function $r(e,s)$, which acts as a barrier: any requirement $R_j$ with $j>2e$ is forbidden from putting numbers into $B$ below this usage.

Injury and Convergence: A requirement $R_j$ (where $j>e$) may attempt to enumerate a number into the oracle that violates the restraint, thereby injuring $R_e$. However, because each requirement $R_e$ is only injured by requirements with higher priority (lower index), and because we define our strategies to act at most finitely often, the restraints eventually stabilize. Each requirement is eventually satisfied, proving the existence of degrees strictly between $0$ and $0^{\prime }$.

Conclusion

The hierarchy of unsolvability is a unified architecture. From the self-referential failure of the Halting Problem, through the quantificational complexity of the arithmetical hierarchy, to the constructive priority arguments of Friedberg-Muchnik, recursion theory demonstrates that the landscape of computation is internally complex and resistant to reduction. These results establish the foundational limits for logic: computational power is not a singular resource, but a partitioned, structured hierarchy that defines the limits of what is knowable through effective procedure.

Works Cited

• Cooper, S. Barry. Computability Theory. Chapman & Hall/CRC, 2004.

• Odifreddi, Piergiorgio. Classical Recursion Theory. North-Holland, 1989.

• Shoenfield, Joseph R. Degrees of Unsolvability. North-Holland, 1971.