TY - GEN
T1 - Semilattices of Punctual Numberings
AU - Bazhenov, Nikolay
AU - Mustafa, Manat
AU - Ospichev, Sergei
N1 - Funding Information:
Part of the research contained in this paper was carried out while the first and the last authors were visiting the Department of Mathematics of Nazarbayev University, Nur-Sultan. The authors wish to thank Nazarbayev University for its hospitality.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020
Y1 - 2020
N2 - The theory of numberings studies uniform computations for classes of mathematical objects. A large body of literature is devoted to investigations of computable numberings, i.e. uniform enumerations for families of computably enumerable sets, and the reducibility among these numberings. This reducibility, induced by Turing computable functions, aims to classify the algorithmic complexity of numberings. The paper is inspired by the recent advances in the area of punctual algebraic structures. We recast the classical studies of numberings in the punctual setting—we study punctual numberings, i.e. uniform computations for families of primitive recursive functions. The reducibility between punctual numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We prove that any infinite Rogers pr-semilattice is dense and does not have minimal elements. Furthermore, we give an example of infinite Rogers pr-semilattice, which is a lattice. These results exhibit interesting phenomena, which do not occur in the classical case of computable numberings and their semilattices.
AB - The theory of numberings studies uniform computations for classes of mathematical objects. A large body of literature is devoted to investigations of computable numberings, i.e. uniform enumerations for families of computably enumerable sets, and the reducibility among these numberings. This reducibility, induced by Turing computable functions, aims to classify the algorithmic complexity of numberings. The paper is inspired by the recent advances in the area of punctual algebraic structures. We recast the classical studies of numberings in the punctual setting—we study punctual numberings, i.e. uniform computations for families of primitive recursive functions. The reducibility between punctual numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We prove that any infinite Rogers pr-semilattice is dense and does not have minimal elements. Furthermore, we give an example of infinite Rogers pr-semilattice, which is a lattice. These results exhibit interesting phenomena, which do not occur in the classical case of computable numberings and their semilattices.
KW - Friedberg numbering
KW - Numbering
KW - Online computation
KW - Primitive recursion
KW - Punctual structure
KW - Rogers semilattice
KW - Upper semilattice
UR - http://www.scopus.com/inward/record.url?scp=85093854226&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85093854226&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-59267-7_1
DO - 10.1007/978-3-030-59267-7_1
M3 - Conference contribution
AN - SCOPUS:85093854226
SN - 9783030592660
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Theory and Applications of Models of Computation - 16th International Conference, TAMC 2020, Proceedings
A2 - Chen, Jianer
A2 - Feng, Qilong
A2 - Xu, Jinhui
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020
Y2 - 18 October 2020 through 20 October 2020
ER -