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

17.03.1963 г.: «
Поставленную Вами задачу о классе порядковых 
чисел, определённых решетом и конструктивным континуумом, мне 
удалось сделать <…>. Оказалось, он 
(класс)
 совпадает с классом 
„конструктивных ординалов“ Чёрча
–
Клини. Однако, названные „кон-
структивные ординалы“ оказываются недостаточно конструктив-
ными».
2.05.1963 г.
 
«Заниматься в ближайшее время думаю двойствен-
ностью между дескриптивными иерархиями и теорией алгоритмов. 
<…>. Есть у меня один принцип двойственности, который нужда-
ется в проверке. Судя по литературе, этими вопросами занимался 
Б.А. Трахтенброт. В частности, этому был посвящён его доклад на 
Всесоюзном математическом съезде (1956 г.), но в „Трудах“ съезда 
–
 
об этом докладе буквально три строчки, по которым понять, насколь-
ко далеко он продвинулся, было невозможно. Поэтому я недели две 
назад написал ему: нельзя ли мне ознакомиться с этим докладом». 
На самом деле эти вещи меня прежде интересовали в связи с 
моими попытками продвинуться в решении проблемы сводимости 
Поста. После решения этой проблемы Мучником и Фридбергом я 
больше не возвращался к упомянутым иерархиям и посоветовал 
Володе обратиться к статье Дж. Аддисона, близкой к наметившей-
ся его диссертационной теме.
20.11.1963 г.
«
Вот уже несколько дней, как я нахожусь в Киеве. 
Операцию обещают примерно через неделю. Получил письмо от 

---

275
Алексей Андреевич и Володя
Б.А. Трахтенброта. Pаботу „Применение прямоугольных решёт“, ко-
торую Вы ему передали, он нашёл достаточно интересной для докла-
да на семинаре „Алгебра и Логика“. Здесь, в Киеве, пробуду, вероятно, 
месяца три».
16.03.1964 г.
«
По возвращении из Киева нашёл дома письмо от 
Б.А. и свою заметку с подробными замечаниями к ней. Это даже не 
замечания, а обстоятельный и очень внимательный разбор, который 
для меня, конечно, очень ценен. Хочу перейти от конкретного решета 
к произвольному рекурсивному прямолинейному решету».
09.07.1964 г.
«
Получил от редакции „Сибирского Математичес-
кого Журнала“ сообщение, что работа поступила к ним». 
(Эта работа 
опубликована позднее как [А1]. 
Б.Т.
). 
В дальнейшем научные интересы Володи стабилизируются на 
проблемах, смежных для ДТМ и теории рекурсии. Он предпочита-
ет диссертационную тему из области эффективной ДТМ. А.А. 
одобряет его выбор и с энтузиазмом стимулирует его работу. При 
этом имеется в виду применение методов теории ДТМ (и в частнос-
ти 
–
R
-операций) для установления свойств рекурсивных иерархий 
и для оценки расширений этих иерархий.