License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2023.11
URN: urn:nbn:de:0030-drops-174725
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17472/
Go to the corresponding LIPIcs Volume Portal

Bazhenov, Nikolay ; Kalociński, Dariusz

Degree Spectra, and Relative Acceptability of Notations

pdf-format:
LIPIcs-CSL-2023-11.pdf (0.8 MB)

Abstract

We investigate the interplay between the degree spectrum of a computable relation R on the computable structure (ω, <), i.e., natural numbers with the standard order, and the computability of the successor, relativized to that relation, in all computable copies of the structure - the property we dub successor’s recoverability. In computable structure theory, this property is used to show that of all possible Turing degrees that could belong to the spectrum of R (namely, of all Δ₂ degrees), in fact only the computably enumerable degrees are contained in the spectrum. Interestingly, successor’s recoverability (in the unrelativized form) appears also in philosophy of computing where it is used to distinguish between acceptable and deviant encodings (notations) of natural numbers. Since Shapiro’s notations are rarely seen through the lens of computable structure theory, we first lay the elementary conceptual groundwork to understand notations in terms of computable structures and show how results pertinent to the former can fundamentally inform our understanding of the latter. Secondly, we prove a new result which shows that for a large class of computable relations (satisfying a certain effectiveness condition), having all c.e. degrees as a spectrum implies that the successor is recoverable from the relation. The recoverability of successor may be otherwise seen as relativized acceptability of every notation for the structure. We end with remarks about connections of our result to relative computable categoricity and to a similar direction pursued by Matthew Harrison-Trainor in [Harrison-Trainor, 2018], and with an open question.

BibTeX - Entry

@InProceedings{bazhenov_et_al:LIPIcs.CSL.2023.11,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz},
  title =	{{Degree Spectra, and Relative Acceptability of Notations}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17472},
  URN =		{urn:nbn:de:0030-drops-174725},
  doi =		{10.4230/LIPIcs.CSL.2023.11},
  annote =	{Keywords: Computable structure theory, Degree spectra, \omega-type order, C.e. degrees, \Delta₂ degrees, Acceptable notation, Successor, Learnability}
}

Keywords: Computable structure theory, Degree spectra, ω-type order, C.e. degrees, Δ₂ degrees, Acceptable notation, Successor, Learnability
Collection: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI