A hypercomputational alien

摘要

Is there a physical constant with the value of the halting function? An answer to this question, as in other discussions of hypercomputation, assumes a fixed interpretation of nature by mathematical entities. Without agreeing on such an interpretation, the question is without context and meaningless.We discuss the subjectiveness of viewing the mathematical properties of nature, and the possibility of comparing computational models having alternate views of the world. For that purpose, we propose a conceptual framework for power comparison, by linking computational models to hypothetical physical devices. Accordingly, we deduce some mathematical notions of relative computational power, allowing for the comparison of arbitrary models over arbitrary domains.In addition, we demonstrate that the method commonly used in the literature for establishing that one model is strictly more powerful than another is problematic, as it can allow for a model to be “more powerful” than itself. On the positive side, we note that Turing machines and the recursive functions are not susceptible to this anomaly, justifying the standard means of showing that a model is more powerful than Turing machines.