Advertisement
Published in:
2006 | OriginalPaper | Chapter
Forecasting Black Holes in Abstract Geometrical Computation is Highly Unpredictable
Author : Jérôme Durand-Lose
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 Σ
$_{\rm 2}^{\rm 0}$
-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The Σ
$_{\rm 2}^{\rm 0}$
-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The Σ
$_{\rm 2}^{\rm 0}$
-membership is proved with a logical characterization.