|
Алгебра и логика, 1974, том 13, номер 1, страницы 22–25
(Mi al1411)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О полной $btt$-степени
Г. Н. Кобзев
Аннотация:
По определению, $A\leqslant_{bd}B$, если найдутся общерекурсивная функция
$f(x)$ и число $k$ такие, что $(\forall x)(|D_{f(x)}|\leqslant k\ \&\ (x\in
A\Leftrightarrow B\cap D_{f(x)}\neq\varnothing))$ (здесь $D_{x}$ —
стандартная нумерация конечных множеств). Если $A\leqslant_{bd}B$ и
$B\leqslant_{bd}A$, то $A\equiv_{bd}B$. Доказывается, что если $K$ —
креативное множество, $A$ — рекурсивно-перечислимое множество, то
условия $K\equiv_{btt}A$ и $K\equiv_{bd}A$ эквивалентны. Из $K\equiv_{bd}A$
следует, что ${}^{k+1}A\leqslant_{m}{}^{k}A$ для некоторого $k$. Однако
существует такое $A$, что $K\equiv_{bd}A$ и $(\forall k)(A^{k}<_mA^{k+1})$.
Поступило: 11.12.1973
Образец цитирования:
Г. Н. Кобзев, “О полной $btt$-степени”, Алгебра и логика, 13:1 (1974), 22–25
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1411 https://www.mathnet.ru/rus/al/v13/i1/p22
|
|