The "paradox" of computability and a recursive relative version of the Busy Beaver function
Not on the map. Why?
Abstract (arXiv)
In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. We will thereby demonstrate the existence of a "paradox" of computability a la Skolem: a function is computable when "seen from the outside" the subsystem, but uncomputable when "seen from within" the same subsystem. Finally, we will raise the possibility of defining universal submachines, and a hierarchy of negative Turing degrees.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 22 Dec 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1.
1 paper.