RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2023 Number 3, Pages 28–35 (Mi vmumm4537)

This article is cited in 2 papers

Mathematics

Two theorems on minimal generally-computable numberings

M. Kh. Faizrahmanov

Scientific-Educational Mathematical Center of Volga Federal District

Abstract: The paper proves that for any set $A$ that computes a non-computable computably enumerable set, any infinite $A$-computable family has an infinite number of pairwise nonequivalent minimal $A$-computable numberings. It is established that an arbitrary set $A\leqslant_T\emptyset '$ is low if and only if any infinite $A$-computable family with the greatest set under inclusion has an infinite number of pairwise nonequivalent positive $A$-computable numberings.

Key words: minimal numbering, positive numbering, computably enumerable set, low set.

UDC: 510.5

Received: 14.11.2022

DOI: 10.55959/MSU0579-9368-1-64-3-5


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2023, 78:3, 136–143

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024