Bounded reducibility for computable numberings.

Nikolay Bazhenov, Manat Mustafa, Sergey Ospichev

Research output: Contribution to journalArticle

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.
Original languageEnglish
Article number1
Pages (from-to)1
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - Jun 19 2019

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

  • Cite this