100 лет со дня рождения

Хотелось бы возмож-
но полнее выяснить связи R-операций с обобщённой вычислимостью.
 
Мне кажется, этот путь должен быть плодотворным. Этой связи 
мне не хватало ещё в прошлогодней работе о сравнении индексов в 
теории R-операций и в теории рекурсивных функционалов, почему я и 
начал эту работу».
В одной из своих последних публикаций (1973 г.) «О методе 
трансфинитных индексов в теории операций над множествами» 
[Л3]
 
Алексей Андреевич сформулировал следующие положения: 
«
Представляется интересным проследить в новом свете
 связь 
 ал горитмических концепций с ДТМ
. Здесь можно отметить два под-
хода:
(i) Первый состоит в том, что рассматриваются различные 
рекур сивные иерархии множеств и их обобщения. В частности R-ие-
рархии изучают сейчас Эндертон и Хинман в США и Амстиславский 
у нас.
(ii) Другой состоит в разработке своего рода
 квазиалгоритми-
ческой точки зрения на задачи классической ДТМ.
 Мне не известны 
никакие работы в этом направлении».
Реакция Володи по поводу второго подхода А.А. звучит в рабо-
тах [А11] и [А12]. 
В предисловии к неопубликованной статье «Вычислимые фун-
кционалы и
R
-операции в континууме» [А12] он пишет:
«
В данной работе продолжается изучение связи между вычисли-
мыми совместными функционалами и известными в дескриптивной 
теории множеств R-оперциями Колмогорова. Первые результаты о 
связи между эффективными R(или R
C
)-множествами и множества-
ми полу-рекурсивными относительно совместных функционалов, были 
получены Хинманом в [1]
3
. Некоторые дальнeйшие pезультаты 
–
 в 
том числе новая рекурсивная характеристика эффективных R
C
-мно-
жеств натуральных чисел 
–
 были получены нами и изложены в [2]
4
. 
Распространению этих результатов на R
C
-подмножества континуу-
ма, рассматриваемые в дескриптивной теории множеств, мешал не-
достаток имевшихcя в литературе сведений по теории вычислимых 
совместных функционалов. Этот недостаток был восполнен в резуль-
3
 P.G. Hinman
. Hierarchies of effective descriptive set theory. Trans. Amer. 
Math. Soc. (1969), 142:111
–
139.
4
 Амстиславский В.И
. Рекурсивность и 
R
C
-
операции
.
Известия АН 
СССР, 1974, т. 8, № 6:1221
–
1237. [А9].

---

283
Алексей Андреевич и Володя
тате работы [3]
5
. 
Теперь на этой основе мы получим рекурсивные 
характеристики R
C
-множеств в некоторых функциональных про-
странствах 
–
 в том числе в пространствах Бэра.
В предшествующих работах рекурсивные характеристики уста-
навливались лишь для эффективных R
C
-множеств [1,2,4 
6
], теперь 
мы получим их не только для эффективных, но и для классических 
R
C
-множеств.