### Abstract

The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility $\leq$ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family $S$ of c.e. sets, its Rogers semilattice $R(S)$ contains the $\leq$-degrees of computable numberings of $S$. Khutoretskii proved that $R(S)$ is always either one-element, or infinite. Selivanov proved that an infinite $R(S)$ cannot be a lattice.

We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.

We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.

Original language | English |
---|---|

Article number | 1 |

Pages (from-to) | 1 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science |

Publication status | Published - Jun 19 2019 |

## Fingerprint Dive into the research topics of 'Bounded reducibility for computable numberings.'. Together they form a unique fingerprint.

## Cite this

Bazhenov, N., Mustafa, M., & Ospichev, S. (2019). Bounded reducibility for computable numberings.

*Lecture Notes in Computer Science*, 1. [1].