ALGORITHMIC PROPERTIES OF ROGERS SEMILATTICES
Date
2024-04-25
Authors
Tleuliyeva, Zhansaya
Journal Title
Journal ISSN
Volume Title
Publisher
Nazarbayev University School of Sciences and Humanities
Abstract
The thesis uses various approaches to explore the algorithmic complexity of families of subsets of natural numbers. One of these approaches involves investigating upper semilattices of computable numberings of a given family and their complexity in different hierarchies. These semilattices, known as Rogers semilattices, can help distinguish different structural properties of families of partial computable functions and computably enumerable sets. As a result, by using Rogers semilattices of computable numberings, we can measure the algorithmic complexity of the corresponding family.
Description
Keywords
Type of access: Open access
Citation
Tleuliyeva, Zh. (2024). Algorithmic properties of Rogers Semilattices. Nazarbayev University School of Sciences and Humanities