solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看427次
Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees. (arXiv:1707.00256v1 [math.LO])
来源于:arXiv
We study the sets that are computable from both halves of some (Martin-L\"of)
random sequence, which we call \emph{$1/2$-bases}. We show that the collection
of such sets forms an ideal in the Turing degrees that is generated by its
c.e.\ elements. It is a proper subideal of the $K$-trivial sets. We
characterise $1/2$-bases as the sets computable from both halves of Chaitin's
$\Omega$, and as the sets that obey the cost function $\mathbf c(x,s) =
\sqrt{\Omega_s - \Omega_x}$.
Generalising these results yields a dense hierarchy of subideals in the
$K$-trivial degrees: For $k< n$, let $B_{k/n}$ be the collection of sets that
are below any $k$ out of $n$ columns of some random sequence. As before, this
is an ideal generated by its c.e.\ elements and the random sequence in the
definition can always be taken to be $\Omega$. Furthermore, the corresponding
cost function characterisation reveals that $B_{k/n}$ is independent of the
particular representation of the rational $k/n$, and that $B_ 查看全文>>