A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are likewise (...) irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems. (shrink)

The ‘Turing barrier’ is an evocative image for 0′, the degree of the unsolvability of the halting problem for Turing machines—equivalently, of the undecidability of Peano Arithmetic. The ‘barrier’ metaphor conveys the idea that effective computability is impaired by restrictions that could be removed by infinite methods. Assuming that the undecidability of PA is essentially depending on the finite nature of its computational means, decidability would be restored by the ω-rule. Hypercomputation, the hypothetical realization of infinitary machines through relativistic and (...) quantium models, would thus be capable of breaking the Turing barrier. The speculation is unfounded in principle, apart from issues of physical realizability: The point is that the ω-rule does not cope with all objects entailing the undecidability of PA. As long as the system is consistent, the computational boundary can be established by paradox-like constructions, such as Gödel-Rosser’s and Yablo’s, which are refractory to infinite induction, and do stand as the barrier’s buttresses. (shrink)

Church's Thesis states the equivalence of computable functions and recursive functions. This can be interpreted as a definition, as an explanation, as an axiom, and as a proposition of mechanistic philosophy. A number of arguments and objections, including a pair of counterexamples based on Gödel's Incompleteness Theorem, allow to conclude that Church's Thesis can be reasonably taken both as a definition and as an axiom, somewhat less convincingly as an explanation, but hardly as a mechanistic proposition.