Geodesic
Recursively compressible sets
Matematičeskie zametki, Tome 64 (1998) no. 1, pp. 9-16 
V. K. Bulitko. Recursively compressible sets. Matematičeskie zametki, Tome 64 (1998) no. 1, pp. 9-16. http://geodesic.mathdoc.fr/item/MZM_1998_64_1_a1/
@article{MZM_1998_64_1_a1,
     author = {V. K. Bulitko},
     title = {Recursively compressible sets},
     journal = {Matemati\v{c}eskie zametki},
     pages = {9--16},
     year = {1998},
     volume = {64},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1998_64_1_a1/}
}
TY  - JOUR
AU  - V. K. Bulitko
TI  - Recursively compressible sets
JO  - Matematičeskie zametki
PY  - 1998
SP  - 9
EP  - 16
VL  - 64
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_1998_64_1_a1/
LA  - ru
ID  - MZM_1998_64_1_a1
ER  - 
%0 Journal Article
%A V. K. Bulitko
%T Recursively compressible sets
%J Matematičeskie zametki
%D 1998
%P 9-16
%V 64
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_1998_64_1_a1/
%G ru
%F MZM_1998_64_1_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

Classes of recursively compressible and incompressible sets as well as some other classes emerging in connection with a simple recursive-theory model of data array packing are studied. Some new completeness criteria for sets are obtained.

[1] Bulitko V. K., “Subtyuringovy svodimosti ogranichennoi slozhnosti”, Izv. vuzov. Matem., 1992, no. 1, 27–37 | MR | Zbl

[2] Solovev V. D., “Struktura raspredeleniya informatsii v beskonechnoi posledovatelnosti”, Diskretnaya matem., 8:2 (1996), 97–107 | Zbl

[3] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[4] Barzdin Ya. M., “Slozhnost programm, raspoznayuschikh prinadlezhnost naturalnykh chisel, ne prevyshayuschikh $n$, rekursivno perechislimomu mnozhestvu”, Dokl. AN SSSR, 182:6 (1968), 1249–1252 | MR | Zbl

[5] Kolmogorov A. N., “Tri podkhoda k opredeleniyu ponyatiya “kolichestvo informatsii””, Problemy peredachi informatsii, 1:1 (1965), 3–11 | MR | Zbl

[6] Martin-Löf P., “Complexity oscillations in infinite binary sequences”, Z. Wahrscheinlichkeitsteorie Verw. Geb., 19:3 (1971), 225–230 | DOI | MR | Zbl

[7] Jockush C. G., Soare R. I., “$\Pi^0_1$-classes and degrees of theories”, Trans. Amer. Math. Soc., 173 (1972), 33–56 | DOI | MR

[8] Loveland D. W., “A variant of the Kolmogorov concept of complexity”, Inform. and Control (Shenyang), 15 (1969), 510–526 | DOI | MR | Zbl