mlsanityData to 14 Oct 2026

The "paradox" of computability and a recursive relative version of the Busy Beaver function

arXiv 1612.07400 ↗First posted 22 Dec 2016cs.LO math.LOcited by 1

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

Cited by year

Citing papers per year: 2021: 1.

1 paper.