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

Algebra Logika, 2003 Volume 42, Number 6, Pages 737–746 (Mi al53)

This article is cited in 8 papers

Positive Numberings of Families of Sets in the Ershov Hierarchy

Zh. T. Talasbaeva

Al-Farabi Kazakh National University

Abstract: It is proved that there exist infinitely many positive undecidable $\Sigma^{-1}_n$-computable numberings of every infinite family $\mathcal S\subseteq\Sigma^{-1}_n$ that admits at least one $\Sigma^{-1}_n$-computable numbering and contains either the empty set, for even $n$, or $N$ for odd $n$.

Keywords: Ershov hierarchy, positive undecidable $\Sigma^{-1}_n$-computable numbering.

UDC: 510.5

Received: 20.08.2001
Revised: 15.07.2003


 English version:
Algebra and Logic, 2003, 42:6, 413–418

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024