TY - JOUR

T1 - Precomplete Numberings

AU - Selivanov, V. L.

PY - 2021/7/1

Y1 - 2021/7/1

N2 - In this survey, we discuss the theory of precomplete numberings, which appear frequently in computability theory. Precomplete numberings are closely related to some versions of the fixed-point theorem having an important methodological value. Sometimes, this allows one to replace cumbersome proofs based on the so-called priority method by elegant and simple applications of this theorem. In a sense, this paper covers the part of computability theory that may be developed by elementary methods.

AB - In this survey, we discuss the theory of precomplete numberings, which appear frequently in computability theory. Precomplete numberings are closely related to some versions of the fixed-point theorem having an important methodological value. Sometimes, this allows one to replace cumbersome proofs based on the so-called priority method by elegant and simple applications of this theorem. In a sense, this paper covers the part of computability theory that may be developed by elementary methods.

KW - 03C57

KW - 03D45

KW - complete numbering

KW - hierarchy

KW - index set

KW - numbering

KW - precomplete numbering

KW - reducibility

KW - universality

UR - http://www.scopus.com/inward/record.url?scp=85106731406&partnerID=8YFLogxK

U2 - 10.1007/s10958-021-05422-2

DO - 10.1007/s10958-021-05422-2

M3 - Article

AN - SCOPUS:85106731406

VL - 256

SP - 96

EP - 124

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 1

ER -