The famous theory of undecidable sentences created by Kurt Godel in 1931 is presented as clearly and as rigorously as possible. Introductory explanations beginning with the necessary facts of arithmetic of integers and progressing to the theory of representability of arithmetical functions and relations in the system (S) prepare the reader for the systematic exposition of the theory of Godel which is taken up in the final chapter and the appendix.

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers (...) by Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

This book is well known for its proof that many mathematical systems - including lattice theory and closure algebras - are undecidable. It consists of three treatises from one of the greatest logicians of all time: "A General Method in Proofs of Undecidability," "Undecidability and Essential Undecidability in Mathematics," and "Undecidability of the Elementary Theory of Groups.".

We show that true first-order arithmetic is interpretable over the real-algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras. From this the undecidability of the structures follows. We also show that Scott's model is equivalent to true second-order arithmetic. In the appendix we argue that undecidability on the language of ordered rings follows from intuitionistically plausible properties of the real numbers.

We argue that it is fundamentally impossible to recover information about quantum superpositions when a quantum system has interacted with a sufficiently large number of degrees of freedom of the environment. This is due to the fact that gravity imposes fundamental limitations on how accurate measurements can be. This leads to the notion of undecidability: there is no way to tell, due to fundamental limitations, if a quantum system evolved unitarily or suffered wavefunction collapse. This in turn provides a (...) solution to the problem of outcomes in quantum measurement by providing a sharp criterion for defining when an event has taken place. We analyze in detail in examples two situations in which in principle one could recover information about quantum coherence: (a) “revivals” of coherence in the interaction of a system with the measurement apparatus and the environment and (b) the measurement of global observables of the system plus apparatus plus environment. We show in the examples that the fundamental limitations due to gravity and quantum mechanics in measurement prevent both revivals from occurring and the measurement of global observables. It can therefore be argued that the emerging picture provides a complete resolution to the measurement problem in quantum mechanics. (shrink)

We argue that it is fundamentally impossible to recover information about quantum superpositions when a quantum system has interacted with a sufficiently large number of degrees of freedom of the environment. This is due to the fact that gravity imposes fundamental limitations on how accurate measurements can be. This leads to the notion of undecidability: there is no way to tell, due to fundamental limitations, if a quantum system evolved unitarily or suffered wavefunction collapse. This in turn provides a (...) solution to the problem of outcomes in quantum measurement by providing a sharp criterion for defining when an event has taken place. We analyze in detail in examples two situations in which in principle one could recover information about quantum coherence: a) “revivals” of coherence in the interaction of a system with the measurement apparatus and the environment and b) the measurement of global observables of the system plus apparatus plus environment. We show in the examples that the fundamental limitations due to gravity and quantum mechanics in measurement prevent both revivals from occurring and the measurement of global observables. It can therefore be argued that the emerging picture provides a complete resolution to the measurement problem in quantum mechanics. (shrink)

In the present paper the well-known Gödels – Churchs argument concerning the undecidability of logic (of the first order functional calculus) is exhibited in a way which seems to be philosophically interestingfi The natural numbers are not used. (Neither Chinese Theorem nor other specifically mathematical tricks are applied.) Only elementary logic and very simple set-theoretical constructions are put into the proof. Instead of the arithmetization I use the theory of concatenation (formalized by Alfred Tarski). This theory proves to be (...) an appropriate tool. The decidability is defined directly as the property of graphical discernibility of formulas. (shrink)

This chapter explores some fundamental consequences of the correspondence between physical process and computations. Most physical questions may be answerable only through irreducible amounts of computation. Those that concern idealized limits of infinite time, volume, or numerical precision can require arbitrarily long computations, and so be considered formally undecidable. The behavior of a physical system may always be calculated by simulating explicitly each step in its evolution. Much of theoretical physics has, however, been concerned with devising shorter methods of calculation (...) that reproduce the outcome without tracing each step. Computational irreducibility is common among the systems investigated in mathematics and computation theory, but it may well be the exception rather than the rule, since most physical questions may be answerable only through irreducible amounts of computation. (shrink)

n the spatialized Prisoner’s Dilemma, players compete against their immediate neighbors and adopt a neighbor’s strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...) will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner’s Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurationns of Prisoner’s Dilemma strategies will take the form of such cellular automata. (shrink)

This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that (...) group may announce simultaneously as well. The logic CAL therefore has some features of game logic and of ATL. We show that when there are multiple agents in the language, the satisfiability problem is undecidable for APAL, GAL, and CAL. In the single agent case, the satisfiability problem is decidable for all three logics. (shrink)

Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.

In this paper, I consider the contribution of Geoffrey Bennington's book, _Scatter 1_, to the ongoing discussion of the political dimension of deconstruction. Focusing on the resonances between Bennington's "politics of politics" and the notion of infrapolitics, I suggest that Bennington's major contribution revolves around the introduction of undecidability into political action and thought.

A field K in a ring language $\mathcal {L}$ is finitely undecidable if $\mbox {Cons}(T)$ is undecidable for every nonempty finite $T \subseteq {\mathtt{Th}}(K; \mathcal {L})$. We extend a construction of Ziegler and (among other results) use a first-order classification of Anscombe and Jahnke to prove every NIP henselian nontrivially valued field is finitely undecidable. We conclude (assuming the NIP Fields Conjecture) that every NIP field is finitely undecidable. This work is drawn from the author’s PhD thesis [48, Chapter 3].

In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...) will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner's Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurations of Prisoner's Dilemma strategies will take the form of such cellular automata. (shrink)

For many, the two key thinkers about science in the twentieth century are Thomas Kuhn and Karl Popper, and one of the key questions in contemplating science is how to make sense of theory change. In Creatively Undecided, philosopher Menachem Fisch defends a new way to make sense of the rationality of scientific revolutions. He argues, loosely following Kuhn, for a strong notion of the framework dependency of all scientific practice, while at the same time he shows how such frameworks (...) can be deemed the possible outcomes of keen rational deliberation along Popperian lines. Fisch's innovation is to call attention to the importance of ambiguity and indecision in scientific change and advancement. Specifically, he backs the problem up, looking not at how we might communicate rationally across an already existing divide but at the rational incentive to create an alternative framework in the first place. Creatively Undecided will be essential reading for philosophers of science, and its vivid case study in Victorian mathematics will draw in historians. (shrink)

We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and (...) can be -complete. These classifications are exact. For first order theories even finite sets of premises can generate such consequence sets in either calculus. (shrink)

For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$.The problem if such recurrent double sequences are ultimately zero is undecidable, even if we restrict it to the class of commutative finite algebras.

We give a new proof of the following result : it is undecidable whether a given calculus, that is a finite set of propositional formulas together with the rules of modus ponens and substitution, axiomatizes the classical logic. Moreover, we prove the same for every superintuitionistic calculus. As a corollary, it is undecidable whether a given calculus is consistent, whether it is superintuitionistic, whether two given calculi have the same theorems, whether a given formula is derivable in a given calculus. (...) The proof is by reduction from the undecidable halting problem for the so-called tag systems introduced by Post. We also give a historical survey of related results. (shrink)

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those (...) in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable. (shrink)

We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...) do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 01–complete. These results go via reduction to problems concerning domino systems. (shrink)

The recent, short debate over the alethic undecidability of a Liar Sentence between Stephen Barker and Mark Jago is revisited. It is argued that Jago’s objections succeed in refuting Barker’s alethic undecidability solution to the Liar Paradox, but that, nevertheless, this approach may be revived as the alethic indeterminacy solution to the Liar Paradox. According to the alethic indeterminacy solution, there is genuine metaphysical indeterminacy as to whether a Liar Sentence bears an alethic property, whether truth or falsity. (...) While the alethic indeterminacy solution is presented here, and some revenge cases are considered and addressed, the primary aim of this paper is to revive and defend this underexplored and auspicious approach to solving the Liar Paradox. (shrink)

Let S be a deductive system such that S-derivability (⊦s) is arithmetic and sound with respect to structures of class K. From simple conditions on K and ⊦s, it follows constructively that the K-completeness of ⊦s implies MP(S), a form of Markov's Principle. If ⊦s is undecidable then MP(S) is independent of first-order Heyting arithmetic. Also, if ⊦s is undecidable and the S proof relation is decidable, then MP(S) is independent of second-order Heyting arithmetic, HAS. Lastly, when ⊦s is many-one (...) complete, MP(S) implies the usual Markov's Principle MP. An immediate corollary is that the Tarski, Beth and Kripke weak completeness theorems for the negative fragment of intuitionistic predicate logic are unobtainable in HAS. Second, each of these: weak completeness for classical predicate logic, weak completeness for the negative fragment of intuitionistic predicate logic and strong completeness for sentential logic implies MP. Beth and Kripke completeness for intuitionistic predicate or sentential logic also entail MP. These results give extensions of the theorem of Gödel and Kreisel (in [4]) that completeness for pure intuitionistic predicate logic requires MP. The assumptions of Godel and Kreisel's original proof included the Axiom of Dependent Choice and Herbrand's Theorem, no use of which is explicit in the present article. (shrink)

In this paper I attempt to clarify a relatively little-studied aspect of Michael Dummett's argument for intuitionism: its use of the notion of ‘undecidable’ sentence. I give a new analysis of this concept in epistemic terms, with which I resolve some puzzles and questions about how it works in the anti-realist critique of classical logic.

We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.

We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.

We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts of Visser’s basic and formal logics, (...) respectively. We also show that, for most “natural” first-order modal logics, the two-variable fragment with a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable, regardless of whether we consider semantics with expanding or constant domains. These include all sublogics of QKTB, QGL, and QGrz—among them, QK, QT, QKB, QD, QK4, and QS4. (shrink)

We show that true first-order arithmetic of the positive integers is interpretable over the real-algebraic structure of Scott's topological model for intuitionistic analysis. From this the undecidability of the structure follows.

This paper provides the first examples of rings of algebraic numbers containing the rings of algebraic integers of the infinite algebraic extensions of where Hilbert's Tenth Problem is undecidable.

Stephen Barker presents a novel approach to solving semantic paradoxes, including the Liar and its variants and Curry’s paradox. His approach is based around the concept of alethic undecidability. His approach, if successful, renders futile all attempts to assign semantic properties to the paradoxical sentences, whilst leaving classical logic fully intact. And, according to Barker, even the T-scheme remains valid, for validity is not undermined by undecidable instances. Barker’s approach is innovative and worthy of further consideration, particularly by those (...) of us who aim to find a solution without logical revisionism. As it stands, however, the approach is unsuccessful, as I shall demonstrate below. (shrink)

We show that the $\mathrm{D_A}$-unification problem is undecidable. That is, given two binary function symbols $\bigoplus$ and $\bigotimes$, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following $\mathrm{D_A}$-axioms hold: \begin{align*}(x \bigoplus y) \bigotimes z &= (x \bigotimes z) \bigoplus (y \bigotimes z),\\x \bigotimes (y \bigoplus z) &= (x \bigotimes y) \bigoplus (x \bigotimes z),\\x \bigoplus (y \bigoplus z) &= (x \bigoplus y) \bigoplus z.\end{align*} Two terms are $\mathrm{D_A}$-unifiable (i.e. an equation (...) is solvable in $\mathrm{D_A}$) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory $\mathrm{D_A}$. This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained. (shrink)

With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In (...) our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras. (shrink)

The undecidability of the first-order theory of diagonalizable algebras is shown here.

Buss, S.R., The undecidability of k-provability, Annals of Pure and Applied Logic 53 75-102. The k-provability problem is, given a first-order formula ø and an integer k, to determine if ø has a proof consisting of k or fewer lines . This paper shows that the k-provability problem for the sequent calculus is undecidable. Indeed, for every r.e. set X there is a formula ø and an integer k such that for all n,ø has a proof of k sequents (...) if and only if n ε X. (shrink)

The unreduced solution to the arbitrary interaction problem, absent in the standard theory framework, reveals many equally real and mutually incompatible system configurations, or "realizations". This is the essence of universal dynamic undecidability, or multivaluedness, and the ensuing causal randomness (unpredictability), non-computability, irreversible time flow (evolution, emergence), and dynamic complexity of every real system, object, or process. This creative undecidability of real-world dynamics provides causal explanations for "quantum mysteries", relativity postulates, cosmological problems, and the huge efficiency of high-complexity (...) phenomena, such as life, intelligence, and consciousness, giving rise to extended applications, far beyond the critical limits of usual science paradigm. (shrink)

We prove that the equational theory of a semigroups becomes undecidable if we add a semilattice structure with a ‘touch of symmetric difference’. As a corollary we obtain that the variety of all Boolean algebras with an associative binary operator has a ‘hereditarily’ undecidable equational theory. Our results have implications in logic, e.g. they imply undecidability of modal logics extending the Lambek Calculus and undecidability of Arrow Logics with an associative arrow modality.

Let G be a finite group, T denote the theory of Z[G]-lattices . It is shown that T is undecidable when there are a prime p and a p-subgroup S of G such that S is cyclic of order p4, or p is odd and S is non-cyclic of order p2, or p = 2 and S is a non-cyclic abelian group of order 8 . More precisely, first we prove that T is undecidable because it interprets the word problem (...) for finite groups; then we lift undecidability from T to T. (shrink)

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, (...) but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems. (shrink)

The results of Cubitt et al. on the spectral gap problem add a new chapter to the issue of undecidability in physics, as they show that it is impossible to decide whether the Hamiltonian of a quantum many-body system is gapped or gapless. This implies, amongst other things, that a reductionist viewpoint would be untenable. In this paper, we examine their proof and a few philosophical implications, in particular ones regarding models and limitative results. In more detail, we examine (...) the way these theorems model many-body quantum systems, and we question what, if anything, is the physical counterpart of the models used by Cubitt et al. We argue that these models are non-representational and that, even if they are so artificial that it is hard to imagine a physical system arising from them, they nonetheless offer an opportunity to learn about the world and the relation between mathematics and reality. On this basis, we draw the conclusion that their results do not undermine the reductionist viewpoint in a strong sense but leave the question open in a weak sense. (shrink)

This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that (...) group may announce simultaneously as well. The logic CAL therefore has some features of game logic and of ATL. We show that when there are multiple agents in the language, the satisfiability problem is undecidable for APAL, GAL, and CAL. In the single agent case, the satisfiability problem is decidable for all three logics. (shrink)