### Abstract

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

### Cite this

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

**Bounded reducibility for computable numberings.** / Bazhenov, Nikolay; Mustafa, Manat; Ospichev, Sergey.

Research output: Contribution to journal › Article

*Lecture Notes in Computer Science*, pp. 1.

}

TY - JOUR

T1 - Bounded reducibility for computable numberings.

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Ospichev, Sergey

PY - 2019/6/19

Y1 - 2019/6/19

N2 - 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.

AB - 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.

M3 - Article

SP - 1

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

M1 - 1

ER -