RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2021 Number 10, Pages 3–14 (Mi ivm9717)

Asymptotic density and computability

I. I. Batyrshin

Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: We show that a set is bi-immune if and only if there are no computable permutations that arrange the set into a generically computable set or an effectively densely computable set. An example of a coarsely computable bi-immune set is constructed. It is also proved that for any set there is a permutation from the same Turing degree that arranges the set into an effectively densely computable set. The upper densities of some sets are studied.

Keywords: asymptotic density, generic complexity, bi-immune set, Turing degree.

UDC: 510.5

Received: 02.11.2020
Revised: 02.11.2020
Accepted: 30.03.2021

DOI: 10.26907/0021-3446-2021-10-3-14


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2021, 65:10, 1–9


© Steklov Math. Inst. of RAS, 2024