Email this article A Generic relation on Recursively Enumerable Sets
- Authors: Rybalov A.N.1,2
-
Affiliations:
- Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Omsk State Technical University
- Issue: Vol 55, No 5 (2016)
- Pages: 387-393
- Section: Article
- URL: https://journals.rcsi.science/0002-5232/article/view/234005
- DOI: https://doi.org/10.1007/s10469-016-9410-9
- ID: 234005
Cite item
Open Access
Access granted
Subscription Access
Abstract
We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets.
About the authors
A. N. Rybalov
Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences; Omsk State Technical University
Author for correspondence.
Email: alexander.rybalov@gmail.com
Russian Federation, ul. Pevtsova 13, Omsk, 644099; pr. Mira 11, Omsk, 644050
Supplementary files
