### 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 R_{bm}(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 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 |
---|---|

Title of host publication | Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings |

Editors | Florin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero |

Publisher | Springer Verlag |

Pages | 96-107 |

Number of pages | 12 |

ISBN (Print) | 9783030229955 |

DOIs | |

Publication status | Published - Jan 1 2019 |

Event | 15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom Duration: Jul 15 2019 → Jul 19 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11558 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Conference on Computability in Europe, CiE 2019 |
---|---|

Country | United Kingdom |

City | Durham |

Period | 7/15/19 → 7/19/19 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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

**Bounded Reducibility for Computable Numberings.** / Bazhenov, Nikolay; Mustafa, Manat; Ospichev, Sergei.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11558 LNCS, Springer Verlag, pp. 96-107, 15th Conference on Computability in Europe, CiE 2019, Durham, United Kingdom, 7/15/19. https://doi.org/10.1007/978-3-030-22996-2_9

}

TY - GEN

T1 - Bounded Reducibility for Computable Numberings

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Ospichev, Sergei

PY - 2019/1/1

Y1 - 2019/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85069464896&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069464896&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-22996-2_9

DO - 10.1007/978-3-030-22996-2_9

M3 - Conference contribution

SN - 9783030229955

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 96

EP - 107

BT - Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings

A2 - Manea, Florin

A2 - Martin, Barnaby

A2 - Paulusma, Daniël

A2 - Primiero, Giuseppe

PB - Springer Verlag

ER -