RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1988, том 27, номер 2, страницы 131–147 (Mi al2009)

Обобщенные вычисления с оракулами

А. Н. Гамова


Аннотация: Изучаются частичные оракулы $\mathcal{F}$, обладающие некоторой трансфинитной структурой, порождаемой условием $\delta\mathcal{F}\leqslant_m^g\tilde{\mathcal{B}}(\mathcal{F})$, где $\tilde{\mathcal{B}}(\mathcal{F})$ обозначает коды незастревающих машин, а сводящая функция $g$ является тотальной $\mathcal{F}$-вычислимой с обрывом цепей.
Доказана слабая фундированность таких оракулов $\mathcal{F}$ (т.е. $\mathcal{F}$-перечислимость множества $\mathcal{F}$-конструктивных ординалов) и их эквивалентность подходящим оракулам из клиниевской теории вычислимых функционалов.

УДК: 517.15

Поступило: 28.10.1986


 Англоязычная версия: DOI: 10.1007/BF01982308

Реферативные базы данных:


© МИАН, 2024