Bazhenov, Nikolay ;
Kalociński, Dariusz
Degree Spectra, and Relative Acceptability of Notations
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 HarrisonTrainor in [HarrisonTrainor, 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:111:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772648},
ISSN = {18688969},
year = {2023},
volume = {252},
editor = {Klin, Bartek and Pimentel, Elaine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17472},
URN = {urn:nbn:de:0030drops174725},
doi = {10.4230/LIPIcs.CSL.2023.11},
annote = {Keywords: Computable structure theory, Degree spectra, \omegatype order, C.e. degrees, \Delta₂ degrees, Acceptable notation, Successor, Learnability}
}
01.02.2023
Keywords: 

Computable structure theory, Degree spectra, ωtype order, C.e. degrees, Δ₂ degrees, Acceptable notation, Successor, Learnability 
Seminar: 

31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Issue date: 

2023 
Date of publication: 

01.02.2023 