|
Алгебра и логика, 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}$-конструктивных ординалов) и их эквивалентность подходящим оракулам из клиниевской теории вычислимых функционалов.
Поступило: 28.10.1986
Образец цитирования:
А. Н. Гамова, “Обобщенные вычисления с оракулами”, Алгебра и логика, 27:2 (1988), 131–147
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2009 https://www.mathnet.ru/rus/al/v27/i2/p131
|
Статистика просмотров: |
Страница аннотации: | 65 | PDF полного текста: | 25 |
|