Rogers semilattices of punctual numberings

Rogers semilattices of punctual numberings Full article

Journal

Mathematical Structures in Computer Science
ISSN: 0960-1295 , E-ISSN: 1469-8072

Output data

Year: 2022, Volume: 32, Number: 2, Pages: 164-188 Pages count : 25 DOI: 10.1017/S0960129522000093

Tags

decidability; Friedberg numbering; online computation; primitive recursion; punctual structure; Rogers semilattice; Theory of numberings; upper semilattice

Authors

Bazhenov N. ¹ , Mustafa M. ² , Ospichev S. ¹

Affiliations

1	Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, Novosibirsk, 630090, Russian Federation
2	Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbay Batyr Avenue, Nur-Sultan, 010000, Kazakhstan

Funding (1)

Министерство науки и высшего образования РФ
Mathematical Center in Akademgorodok

075-15-2019-1613, 075-15-2022-281

The paper works within the framework of punctual computability, which is focused on eliminating unbounded search from constructions in algebra and infinite combinatorics. We study punctual numberings, that is, uniform computations for families S of primitive recursive functions. The punctual reducibility between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We show that any infinite, uniformly primitive recursive family S induces an infinite Rogers pr-semilattice R. We prove that the semilattice R does not have minimal elements, and every nontrivial interval inside R contains an infinite antichain. In addition, every non-greatest element from R is a part of an infinite antichain. We show that the Σ1 -fragment of the theory Th(R) is decidable.

Bazhenov N. , Mustafa M. , Ospichev S.
Rogers semilattices of punctual numberings
Mathematical Structures in Computer Science. 2022. V.32. N2. P.164-188. DOI: 10.1017/S0960129522000093 WOS Scopus РИНЦ OpenAlex

Web of science:	WOS:000774642000001
Scopus:	2-s2.0-85128149845
Elibrary:	48428493
OpenAlex:	W4220772554

DB	Citing
Scopus	3
Web of science	3
OpenAlex	3
Elibrary	3