Abstract

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