This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) and Wang (1955) in (...) order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth. (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)

We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

Guided by questions of scope, this paper provides an overview of what is known about both the scope and, consequently, the limits of Gödel’s famous first incompleteness theorem.