Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for (...) any ideal of the r.e. degrees. (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)

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)

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

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].

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.

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.

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)

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)

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 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.

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 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)

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.

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.

We show the undecidability of the equational theories of some classes of BAOs with a non-associative, residuated binary extra-Boolean operator. These results solve problems in Jipsen [9], Pratt [21] and Roorda [22], [23]. This paper complements Andréka-Kurucz-Németi-Sain-Simon [3] where the emphasis is on BAOs with an associative binary operator.

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)

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)

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 show that the Π 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.

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)

By using algebraic properties of (commutative unital) indecomposable polynomial rings we achieve results concerning their first-order theory, namely: interpretability of arithmetic and a uniform proof of undecidability of their full theory, both in the language of rings without parameters. This vastly extends the scope of a method due to Raphael Robinson, which deals with a restricted class of polynomial integral domains.

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)

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)

"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)

In vol. 2 of Grundlagen der Mathematik Hilbert and Bernays carry out their undecid- ability proof of predicate logic basing it on their undecidability proof of the arithmeti- cal systemZ00. In this paper, the latter proof is reconstructed and summarized within a formal derivation schema. Formalizing the proof makes the presumed use of a meta language explicit by employing formal predicates as propositional functions, with ex- pressions as their arguments. In the final section of the paper, the proof is (...) analyzed critically by applying Wittgenstein’s view on meta language, which does not lead to a questioning of the assumptions on which the proof is based but of its presumed use of meta language. Finally, it will be argued that determining if it is the undecidability proof or Wittgenstein’s analysis of meta language that is right depends on whether a decision procedure for a predicate that undecidability proofs have seemingly proven undecidable can nonetheless be defined. Thus serious attempts to define a procedure for such a predicate should not be ruled out without studying them. (shrink)

We construct an existentially undecidable complete discretely valued field of mixed characteristic with existentially decidable residue field and decidable algebraic part, answering a question by Anscombe–Fehm in a strong way. Along the way, we construct an existentially decidable field of positive characteristic with an existentially undecidable finite extension, modifying a construction due to Kesavan Thanagopal.

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.

In this article I will consider John D. Caputo’s ‘radical hermeneutics’, with ‘undecidability’ as its major theme, in conversation with Martin Heidegger’s notion of ‘anticipatory resoluteness’. Through an examination of the positions of Caputo and Heidegger I argue that Heidegger’s notion of ‘anticipatory resoluteness’ reaches far beyond the claims of ‘radical hermeneutics’, and that it assumes a reconstructive process which carries within its scope the overtones of deconstruction, the experience of repetition and authenticity and also the implications of Gelassenheit. (...) Further, I am arguing that Caputo’s ‘radical hermeneutics’ is problematic and even erroneous when it comes to criticize Heidegger’s thought portraying it as being founded on ‘the myth of the early Greeks’. (shrink)

It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both for satisfiability, (...) and for satisfiability in finite structures. Moreover most of them are hard for $\Sigma^1_1$ , the first level of the analytical hierachy, and thus have a much higher degree of undecidability than first-order logic. (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)

In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

The product of two $\textbf {Alt}$ logics possesses the polynomial product finite model property and its membership problem is $\textbf {coNP}$-complete. Using a reduction from an undecidable domino-tiling problem, we prove that its admissibility problem is undecidable.

If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.

We prove that the second order predicate unification problem is undecidable by reducing the second order term unification problem to it.

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.

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.

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)

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)

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)

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(G) 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)

Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is (...) proved by means of the phase semantics. (shrink)

Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...) and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-. (shrink)

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