RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2018 Volume 57, Number 4, Pages 426–447 (Mi al857)

This article is cited 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.

UDC: 510.54

Received: 11.02.2017
Revised: 29.01.2018

DOI: 10.17377/alglog.2018.57.402


 English version:
Algebra and Logic, 2018, 57:4, 275–288

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024