On Hypercomputation, Universal and Diagonalization Complete Problems
Eugene Eberbach · Fundamenta Informaticae · 2015
In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are ℋ-complete (hypercomputation complete). We propose also two other classes: 𝒰-complete (universal complete) and 𝒟-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.