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.
Original languageEnglish
Pages (from-to)96-124
Number of pages29
JournalJournal of Mathematical Sciences (United States)
Volume256
Issue number1
DOIs
StatePublished - 1 Jul 2021

    Research areas

  • 03C57, 03D45, complete numbering, hierarchy, index set, numbering, precomplete numbering, reducibility, universality

ID: 126991092