Search results for 'Undecidability' (try it on Scholar)

327 found
Order:
See also:
  1.  91
    Mark Jago (2016). Alethic Undecidability Doesn’T Solve the Liar. Analysis 76 (3):278-283.
    Stephen Barker (2014) 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 (truth, falsity, gap or glut) 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  2. Justin Clarke-Doane (2013). What is Absolute Undecidability?†. Noûs 47 (3):467-481.
    It is often alleged that, unlike typical axioms of mathematics, the Continuum Hypothesis (CH) is indeterminate. This position is normally defended on the ground that the CH is undecidable in a way that typical axioms are not. Call this kind of undecidability “absolute undecidability”. In this paper, I seek to understand what absolute undecidability could be such that one might hope to establish that (a) CH is absolutely undecidable, (b) typical axioms are not absolutely undecidable, and (c) (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  3.  68
    Y. Sato & T. Ikegami (2004). Undecidability in the Imitation Game. Minds and Machines 14 (2):133-43.
    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, (...)
    Direct download (19 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  4.  39
    Patrick Grim (1997). The Undecidability of the Spatialized Prisoner's Dilemma. Theory and Decision 42 (1):53-80.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  5.  12
    Sylvie Avakian (2015). Undecidability’ or ‘Anticipatory Resoluteness’ Caputo in Conversation with Heidegger. International Journal for Philosophy of Religion 77 (2):123-139.
    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. (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  6.  15
    Rodolfo Gambini, Luis Pedro García Pintos & Jorge Pullin (2010). Undecidability and the Problem of Outcomes in Quantum Measurements. Foundations of Physics 40 (1):93-115.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  7.  6
    Miklós Erdélyi-Szabó (2000). Undecidability of the Real-Algebraic Structure of Models of Intuitionistic Elementary Analysis. Journal of Symbolic Logic 65 (3):1014-1030.
    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.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  8. Miklós Erdélyi-Szabó (1998). Undecidability of the Real-Algebraic Structure of Scott's Model. Mathematical Logic Quarterly 44 (3):344-348.
    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.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  9.  35
    Leon Horsten & Philip Welch (2007). The Undecidability of Propositional Adaptive Logic. Synthese 158 (1):41 - 60.
    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 (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  10.  30
    Thomas Brihaye (2006). A Note on the Undecidability of the Reachability Problem for o‐Minimal Dynamical Systems. Mathematical Logic Quarterly 52 (2):165-170.
    In this paper we prove that the reachability problem is BSS-undecidable for o-minimal dynamical systems.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  11.  6
    Ying‐Fang Kao, V. Ragupathy, K. Vela Velupillai & Stefano Zambelli (2012). Noncomputability, Unpredictability, Undecidability, and Unsolvability in Economic and Finance Theories. Complexity 18 (1):51-55.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  12.  46
    Peter Koellner (2010). On the Question of Absolute Undecidability. In Kurt Gödel, Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.), Philosophia Mathematica. Association for Symbolic Logic 153-188.
    The paper begins with an examination of Gödel's views on absolute undecidability and related topics in set theory. These views are sharpened and assessed in light of recent developments. It is argued that a convincing case can be made for axioms that settle many of the questions undecided by the standard axioms and that in a precise sense the program for large cardinals is a complete success “below” CH. It is also argued that there are reasonable scenarios for settling (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   8 citations  
  13.  58
    Andrzej Grzegorczyk (2005). Undecidability Without Arithmetization. Studia Logica 79 (2):163 - 230.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  14.  7
    Klaus Ambos-Spies & Richard A. Shore (1993). Undecidability and 1-Types in the Recursively Enumerable Degrees. Annals of Pure and Applied Logic 63 (1):3-37.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  15.  4
    Erich Grädel, Martin Otto & Eric Rosen (1999). Undecidability Results on Two-Variable Logics. Archive for Mathematical Logic 38 (4-5):313-354.
    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, (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  16.  70
    Jack Reynolds (2002). Habituality and Undecidability: A Comparison of Merleau-Ponty and Derrida on the Decision. International Journal of Philosophical Studies 10 (4):449 – 466.
    This essay examines the relationship that obtains between Merleau-Ponty and Derrida through exploring an interesting point of dissension in their respective accounts of decision-making. Merleau-Ponty's early philosophy emphasizes the body-subject's tendency to seek an equilibrium with the world (by acquiring skills and establishing what he refers to as 'intentional arcs'), and towards deciding in an embodied and habitual manner that minimizes any confrontation with what might be termed a decision-making aporia. On the other hand, in his later writings, Derrida frequently (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  17.  4
    T. Ågotnes, H. van Ditmarsch & T. French (2016). The Undecidability of Quantified Announcements. Studia Logica 104 (4):597-640.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  18.  11
    Franco Montagna (1980). The Undecidability of the First-Order Theory of Diagonalizable Algebras. Studia Logica 39 (4):355 - 359.
    The undecidability of the first-order theory of diagonalizable algebras is shown here.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  19.  4
    Samuel R. Buss (1991). The Undecidability of K-Provability. Annals of Pure and Applied Logic 53 (1):75-102.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20.  12
    Stuart Dalton (1998). Unity and Undecidability. Philosophy in the Contemporary World 5 (4):25-32.
    This essay argues that, in the first Critique, the need for unity leads Kant to re-inscribe the subject in a situation of multiplicity and undecidability. The result, however, is not a relativization that negates the meaning of the subject’s existence, but rather a contextualization that makes meaning possible. This reading clarifies some of the connections between Kant and contemporary postmodernism, especially the work of Jacques Derrida.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  21.  2
    I. Nemeti, I. Sain & A. Simon (1995). Undecidability of the Equational Theory of Some Classes of Residuated Boolean Algebras with Operators. Logic Journal of the IGPL 3 (1):93-105.
    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.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  22.  5
    Carlo Toffalori (1997). An Undecidability Theorem for Lattices Over Group Rings. Annals of Pure and Applied Logic 88 (2-3):241-262.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  23. Patrick Grim, Undecidability in the Spatialized Prisoner's Dilemma: Some Philosophical Implications.
    A version of this paper was presented at the IEEE International Conference on Computational Intelligence, combined meeting of ICNN, FUZZ-IEEE, and ICEC, Orlando, June-July, 1994, and an earlier form of the result is to appear as "The Undecidability of the Spatialized Prisoner's Dilemma" in Theory and Decision . An interactive form of the paper, in which figures are called up as evolving arrays of cellular automata, is available on DOS disk as Research Report #94-04i . An expanded version appears (...)
     
    Export citation  
     
    My bibliography  
  24.  8
    Robin Hirsch & Marcel Jackson (2012). Undecidability of Representability as Binary Relations. Journal of Symbolic Logic 77 (4):1211-1244.
    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.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  25.  7
    J. Siekmann & P. Szabó (1989). The Undecidability of the DA-Unification Problem. Journal of Symbolic Logic 54 (2):402 - 414.
    We show that the 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 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  26. J. Siekmann & P. Szabo (1989). The Undecidability of the $Mathrm{D}_mathrm{A}$-Unification Problem. Journal of Symbolic Logic 54 (2):402-414.
    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 (...)
     
    Export citation  
     
    My bibliography  
  27. Sheryl Silibovsky Brady & Jeffrey B. Remmel (1987). The Undecidability of the Lattice of R.E. Closed Subsets of an Effective Topological Space. Annals of Pure and Applied Logic 35 (2):193-203.
    The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  28.  1
    G. V. Bokov (2015). Undecidability of the Problem of Recognizing Axiomatizations for Propositional Calculi with Implication. Logic Journal of the IGPL 23 (2):341-353.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  29. Stephen Wolfram (forthcoming). 21 Undecidability and Intractability in Theoretical Physics. Emergence: Contemporary Readings in Philosophy and Science.
    No categories
     
    Export citation  
     
    My bibliography   8 citations  
  30.  10
    Mark Jago (2016). Alethic Undecidability Doesn’T Solve the Liar. Analysis 76 (3):278-283.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  31. Gregory Cherlin & Moshe Jarden (1986). Undecidability of Some Elementary Theories Over Pac Fields. Annals of Pure and Applied Logic 30 (2):137-163.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  32. Stephen Barker (2014). Semantic Paradox and Alethic Undecidability. Analysis 74 (2):201-209.
    I use the principle of truth-maker maximalism to provide a new solution to the semantic paradoxes. According to the solution, AUS, its undecidable whether paradoxical sentences are grounded or ungrounded. From this it follows that their alethic status is undecidable. We cannot assert, in principle, whether paradoxical sentences are true, false, either true or false, neither true nor false, both true and false, and so on. AUS involves no ad hoc modification of logic, denial of the T-schema's validity, or obvious (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  33.  9
    Joseph S. Miller & Lawrence S. Moss (2005). The Undecidability of Iterated Modal Relativization. Studia Logica 79 (3):373 - 407.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   9 citations  
  34. M. Boffa (1998). More on an Undecidability Result of Bateman, Jockusch and Woods. Journal of Symbolic Logic 63 (1):50.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  35. Solomon Garfunkel & Herbert Shank (1971). On the Undecidability of Finite Planar Graphs. Journal of Symbolic Logic 36 (1):121-126.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  36. Hilary Putnam (1957). Decidability and Essential Undecidability. Journal of Symbolic Logic 22 (1):39-54.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  37. Dharmendra Kumar (1969). Neutrality, Contingency and Undecidability. British Journal for the Philosophy of Science 19 (4):353-356.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  38. V. Yu Shavrukov (1997). Undecidability in Diagonalizable Algebras. Journal of Symbolic Logic 62 (1):79-116.
    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.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  39.  34
    Andrea Cantini (2003). The Undecidability of Grisin's Set Theory. Studia Logica 74 (3):345 - 368.
    We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  40.  12
    Alasdair Urquhart (1984). The Undecidability of Entailment and Relevant Implication. Journal of Symbolic Logic 49 (4):1059-1073.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   14 citations  
  41. J. Hughes, P. Kroes & S. Zwart (2007). L. HORSTEN and P. WELCH/The Undecidability of Propositional Adaptive Logic 41. Synthese 158 (1):158.
     
    Export citation  
     
    My bibliography   4 citations  
  42.  30
    Franco Montagna & Hiroakira Ono (2002). Kripke Semantics, Undecidability and Standard Completeness for Esteva and Godo's Logic MTL∀. Studia Logica 71 (2):227-245.
    The present paper deals with the predicate version MTL of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono''s Kripke semantics for the predicate version of FLew (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL and classical predicate logic is undecidable. Finally, we prove that MTL is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  43.  5
    Evgeny Zolin (2014). Undecidability of the Problem of Recognizing Axiomatizations of Superintuitionistic Propositional Calculi. Studia Logica 102 (5):1021-1039.
    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. (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  44.  65
    Alexander Chagrov & Michael Zakharyaschev (1993). The Undecidability of the Disjunction Property of Propositional Logics and Other Related Problems. Journal of Symbolic Logic 58 (3):967-1002.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  45.  67
    Saul A. Kripke (1962). The Undecidability of Monadic Modal Quantification Theory. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 8 (2):113-116.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  46.  67
    Panu Raatikainen (2000). Algorithmic Information Theory and Undecidability. Synthese 123 (2):217-225.
    Algorithmic information theory, or the theory of Kolmogorov complexity, has become an extraordinarily popular theory, and this is no doubt due, in some part, to the fame of Chaitin’s incompleteness results arising from this field. Actually, there are two rather different results by Chaitin: the earlier one concerns the finite limit of the provability of complexity (see Chaitin, 1974a, 1974b, 1975a); and the later is related to random reals and the halting probability (see Chaitin, 1986, 1987a, 1987b, 1988, 1989.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  47.  26
    Matthew W. Parker (2003). Undecidability in Rn: Riddled Basins, the KAM Tori, and the Stability of the Solar System. Philosophy of Science 70 (2):359-382.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  48.  10
    Newton Ca da Costa, Francisco A. Doria & Marcelo Tsuji (1995). The Undecidability of Formal Definitions in the Theory of Finite Groups. Bulletin of the Section of Logic 24:56-63.
    Direct download  
     
    Export citation  
     
    My bibliography   2 citations  
  49.  54
    Mingzhong Cai, Richard A. Shore & Theodore A. Slaman (2012). The N-R.E. Degrees: Undecidability and Σ1substructures. Journal of Mathematical Logic 12 (01):1250005-.
  50.  76
    Yves Lafont (1996). The Undecidability of Second Order Linear Logic Without Exponentials. Journal of Symbolic Logic 61 (2):541-548.
    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 (...)
    Direct download (9 more)  
     
    Export citation  
     
    My bibliography  
1 — 50 / 327