Non-Turing Computations Via Malament–Hogarth Space-Times
Non-Turing Computations Via Malament–Hogarth Space-Times
复制标题
通过 Malament–Hogarth 时空进行非图灵计算
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
I. Németi
中科院分区：
文献类型：
--
作者：
G. Etesi;I. Németi
我们研究了Church-Kalmár-Kreisel-Turing关于未来计算机和演绎科学的（必要的）限制的理论命题，鉴于经典广义相对论的最新结果。我们认为，（i）有几个杰出的教会图灵型论文（不仅一个）和（ii）这些论文的有效性取决于我们选择使用的背景物理理论。特别是，如果我们选择经典的广义相对论作为我们的背景理论，那么上述的限制（由这些命题所预言的）就不再是必要的，因此丘奇-图灵命题的某些形式就不再有效（在广义相对论中）。(For背景理论的其他选择，答案可能不同。我们还期待在各种“障碍”计算非递归函数（依靠相对论现象）发表在文献中，并表明，他们可以避免（通过改善我们未来的计算机的“设计”）。我们还要问自己，这一切如何反映在不可计算函数的算术层次和分析层次上。
We investigate the Church–Kalmár–Kreisel–Turing theses theoretical concerning (necessary) limitations of future computers and of deductive sciences, in view of recent results of classical general relativity theory. We argue that (i) there are several distinguished Church–Turing-type theses (not only one) and (ii) validity of some of these theses depend on the background physical theory we choose to use. In particular, if we choose classical general relativity theory as our background theory, then the above-mentioned limitations (predicted by these theses) become no more necessary, hence certain forms of the Church–Turing thesis cease to be valid (in general relativity). (For other choices of the background theory the answer might be different.) We also look at various “obstacles” to computing a nonrecursive function (by relying on relativistic phenomena) published in the literature and show that they can be avoided (by improving the “design” of our future computer). We also ask ourselves, how all this reflects on the arithmetical hierarchy and the analytical hierarchy of uncomputable functions.