A Hierarchy below the Halting Problem for Additive Machines
We answer the question posed by Klaus Meer and Martin Ziegler in "Uncomputability below the Real Halting Problem" whether the set of rational numbers is strictly easier than the Halting Problem with respect to additive machines. We define a hierarchy below the Halting Problem such that the set of rational numbers is strictly easier than the new problems. Moreover, every problem of the hierarchy is strictly easier than its successor.
halting problem additive machines bss model post's problem turing degrees