RPI Researcher Turns Undecidability From a Wall Into a Structured Landscape
A new proposal to classify undecidable problems into three complete complexity classes, borrowing the NP-complete playbook to map what lies past the halting problem.
ProTakeaways
- Eberbach proposes three complexity classes for undecidable problems: U-complete, D-complete, H-complete, modeled on NP-complete.
- Introduces a measure of undecidability as the fraction of input instances that cannot be decided.
- Answers the REC vs RE analog of P vs NP negatively, unlike the still-open P vs NP.
- Extends Turing oracle machines into a general class of super-Turing hypercomputation models.
- Gives a shorter proof of the Entscheidungsproblem using Cantor's uncountability argument directly.
- Hypothesizes an infinite Cantor-style hierarchy of undecidable complexity classes above H-complete.
For decades, computer science has treated undecidability as a wall. A problem is either solvable by a Turing machine or it is not, and the conversation tends to end at the proof of the second case. A new paper argues that stopping there is a bit like defining NP-complete and never talking about anything harder than SAT. It proposes an explicit taxonomy of undecidable problems, complete with reductions, canonical representatives, and an equivalent to the P vs NP question that turns out to have a straightforward answer.
The paper, by Eugene Eberbach of Rensselaer Polytechnic Institute, revisits Turing's 1936 blueprint and asks why we have a rich vocabulary for intractable problems (P, NP, NP-complete, PSPACE) but almost nothing formal for the far larger universe of problems no algorithm can solve at all.
Undecidability was one big bucket
The typical belief is that proving a specific problem TM-undecidable ends any attempt to solve it. In practice, textbooks split undecidable problems into two rings: recursively enumerable but not recursive (RE minus REC), where a machine can confirm yes but never confirm no, and non-RE, where neither the language nor its complement is decidable. Beyond that coarse split, there is no NP-complete style structure.
Eberbach argues this is odd, since reduction techniques are commonly used on undecidable problems without any explicit definition of the classes those reductions are moving between. The paper's core move is to fix that gap.
A degree of undecidability
The first proposal is a quantitative measure. Rather than tagging a problem as simply undecidable, you look at the probability distribution of its inputs and count what fraction of instances are undecidable versus decidable. A problem that is 100% undecidable has every input instance undecidable and none decidable, while recursive problems sit at 0%. Recursively enumerable languages can land anywhere in between.