An explicit solution to Post's Problem over the reals
An explicit solution to Post's Problem over the reals
复制标题
实数上的波斯特问题的显式解
DOI：
10.1016/j.jco.2006.09.004
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
K. Meer;M. Ziegler
在实数计算的BSS模型中，我们证明了一种具体而显式的半可判定语言是不可判定的，但也不能从实停止语言中约简(因此严格地比它更容易)。在实数上Post问题的这种解决方案与它的经典离散变体有很大的不同，在经典离散变体中，先进的对角化技术只有在已知的情况下才能产生这种中间图灵度的存在。然后，我们加强了上述结果，并证明了在BSS模型中，在实际停顿问题下存在不可数个不可比的半可判定图灵度。同样，我们的证明将给出代表这些不同程度的具体问题。最后我们给出了线性盲源分离模型的相应结果，即Over(R，+，-，<；)而不是(R，+，-，×，？，<；)。
In the BSS model of real number computations we prove a concrete and explicit semi-decidable language to be undecidable yet not reducible from (and thus strictly easier than) the real Halting Language. This solution to Post's Problem over the reals significantly differs from its classical, discrete variant where advanced diagonalization techniques are only known to yield the existence of such intermediate Turing degrees. Then we strengthen the above result and show as well the existence of an uncountable number of incomparable semi-decidable Turing degrees below the real Halting Problem in the BSS model. Again, our proof will give concrete such problems representing these different degrees. Finally we show the corresponding result for the linear BSS model, that is over (R,+,-,<) rather than (R,+,-,×,÷,<).