|
This article is cited in 4 scientific papers (total in 4 papers)
Some absolute properties of $A$-computable numberings
S. A. Badaeva, A. A. Issakhovab a Al-Farabi Kazakh National University, Al-Farabi Ave. 71, Alma-Ata, 050038 Kazakhstan
b Kazkh-British Technical University, ul. Tole bi 59, Alma-Ata, 050000 Kazakhstan
Abstract:
For an arbitrary set $A$ of natural numbers, we prove the following statements: every finite family of $A$-computable sets containing a least element under inclusion has an $A$-computable universal numbering; every infinite $A$-computable family of total functions has (up to $A$-equivalence) either one $A$-computable Friedberg numbering or infinitely many such numberings; every $A$-computable family of total functions which contains a limit function has no $A$-computable universal numberings, even with respect to $A$-reducibility.
Keywords:
$A$-computable numbering, $A$-computable Friedberg numbering, $A$-computable universal numbering, $A$-reducibility.
Received: 11.02.2017 Revised: 29.01.2018
Citation:
S. A. Badaev, A. A. Issakhov, “Some absolute properties of $A$-computable numberings”, Algebra Logika, 57:4 (2018), 426–447; Algebra and Logic, 57:4 (2018), 275–288
Linking options:
https://www.mathnet.ru/eng/al857 https://www.mathnet.ru/eng/al/v57/i4/p426
|
Statistics & downloads: |
Abstract page: | 290 | Full-text PDF : | 64 | References: | 38 | First page: | 19 |
|