×

zbMATH — the first resource for mathematics

Positive computable numberings. (English. Russian original) Zbl 0815.03030
Russ. Acad. Sci., Dokl., Math. 48, No. 2, 268-270 (1994); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 332, No. 2, 142-143 (1993).
The concept of a minimal numbering in a Rogers semilattice is the dual concept to universal numberings. The investigation of minimal numberings goes back to the fundamental work of R. Friedberg [J. Symb. Log. 23, 309-316 (1959; Zbl 0088.016)], who proved the existence of a single- valued computable numbering for a family of RE sets, and to the work of Mal’tsev, Pour-El, Ershov, and others.
Our investigation is close to this direction and is devoted to the solution of a problem of I. A. Lavrov [Logic, Found. Math., Comput. Theory; Proc. 5th Int. Congr., London/Ontario 1975, Part 1, 195-206 (1977; Zbl 0386.03023)] on the possible number of positive computable numberings.

MSC:
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite