Bounded Reducibility for Computable Numberings

Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ≤ 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 ≤ -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 ≤ bm. We show that Rogers semilattices Rbm(S), induced by ≤ 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≥ 2, there is a finite family S of c.e. sets such that its semilattice Rbm(S) has precisely 2 n- 1 elements. Furthermore, there is a computable family T of c.e. sets such that Rbm(T) is an infinite lattice.

Original languageEnglish
Title of host publicationComputing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
EditorsFlorin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero
PublisherSpringer Verlag
Pages96-107
Number of pages12
ISBN (Print)9783030229955
DOIs
Publication statusPublished - Jan 1 2019
Event15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom
Duration: Jul 15 2019Jul 19 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11558 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Conference on Computability in Europe, CiE 2019
CountryUnited Kingdom
CityDurham
Period7/15/197/19/19

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Bazhenov, N., Mustafa, M., & Ospichev, S. (2019). Bounded Reducibility for Computable Numberings. In F. Manea, B. Martin, D. Paulusma, & G. Primiero (Eds.), Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings (pp. 96-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11558 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-22996-2_9