
doi: 10.1007/11750321_61
In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability: any recursively enumerable set can be decided in finite time. To achieve this, a Zeno-like construction is used to provide an accumulation similar in effect to the black holes of the black hole model. We prove here that forecasting an accumulation is $\Sigma_2^0$-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The $\Sigma_2^0$-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The $\Sigma_2^0$-membership is proved with a logical characterization.
Black hole model : Energy conservation, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Zeno phenomena, Arithmetical hierarchy, Abstract geometrical computation, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Super-Turing computation, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Turing universality, Accumulation forecasting
Black hole model : Energy conservation, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Zeno phenomena, Arithmetical hierarchy, Abstract geometrical computation, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Super-Turing computation, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Turing universality, Accumulation forecasting
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
