The degree-spectrum characterization of successor recoverability for computable block functions

From papers

Let ff be a computable block function on (ω,<)(\omega,<), and consider the degree spectrum of ff on (ω,<)(\omega,<). The successor is recoverable from ff on (ω,<)(\omega,<) when it can be computed from ff in the relevant presentation.

Degree-spectrum conjecture. If the degree spectrum of ff on (ω,<)(\omega,<) is equal to all c.e. degrees, then the successor is recoverable from ff on (ω,<)(\omega,<).

This would extend the equivalence between the c.e.-degree-spectrum property and successor recoverability beyond the classes covered by the paper's main theorem, to all computable block functions. The source does not state a resolution, so the conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Nikolay Bazhenov and Dariusz Kalociński, “Relatively acceptable notation”, arXiv:2205.00791 (2022).

Solutions 0

No solutions have been posted yet.