Search results for 'Unsolvability (Mathematical logic' (try it on Scholar)

35 found
Order:
  1. Dick Epstein (1975). Cooper S. B.. Degrees of Unsolvability Complementary Between Recursively Enumerable Degrees, Part I. Annals of Mathematical Logic, Vol. 4 No. 1 , Pp. 31–73. [REVIEW] Journal of Symbolic Logic 40 (1):86.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  2. Carl G. Jockusch (1985). Lerman Manuel. Degrees of Unsolvability. Local and Global Theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Heidelberg, New York, and Tokyo, 1983, Xiii + 307 Pp. [REVIEW] Journal of Symbolic Logic 50 (2):549-550.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  3.  6
    Paul C. Rosenbloom (1950). The Elements of Mathematical Logic. New York]Dover Publications.
    An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's theorem (...)
    Direct download  
     
    Export citation  
     
    My bibliography   10 citations  
  4.  86
    Martin Davis (1958). Computability & Unsolvability. Dover.
    Classic text considersgeneral theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   82 citations  
  5.  81
    Martin Davis (ed.) (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.
    "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 (...)
    Direct download  
     
    Export citation  
     
    My bibliography   32 citations  
  6.  2
    M. Lerman (1983). Degrees of Unsolvability: Local and Global Theory. Springer-Verlag.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   21 citations  
  7.  13
    Joseph R. Shoenfield (1972). Degrees of Unsolvability. New York, American Elsevier.
  8.  7
    Richard L. Epstein (1979). Degrees of Unsolvability: Structure and Theory. Springer-Verlag.
    The contributions in the book examine the historical and contemporary manifestations of organized crime, the symbiotic relationship between legitimate and ...
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography   4 citations  
  9.  4
    Amélie Gheerbrant & Marcin Mostowski (2006). Recursive Complexity of the Carnap First Order Modal Logic C. Mathematical Logic Quarterly 52 (1):87-94.
    We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  10.  5
    Harry R. Lewis (1979). Unsolvable Classes of Quantificational Formulas. Addison-Wesley Pub. Co..
    Direct download  
     
    Export citation  
     
    My bibliography   9 citations  
  11.  3
    Burton Dreben (1979). The Decision Problem: Solvable Classes of Quantificational Formulas. Addison-Wesley, Advanced Book Program.
    Direct download  
     
    Export citation  
     
    My bibliography   7 citations  
  12.  1
    F. B. Cannonito (1968). Tennenbaum S.. Degree of Unsolvability and the Rate of Growth of Functions. Proceedings of the Symposium on Mathematical Theory of Automata, New York, N.Y., April 24, 25, 26, 1962, Microwave Research Institute Symposia Series Vol. 12, Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, N.Y., 1963, Pp. 71–73. [REVIEW] Journal of Symbolic Logic 32 (4):524.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  13.  1
    J. C. Shepherdson (1968). Fridman A. A.. Stépéni Nérazréšimosti Problémy Toždéstva V Konéčno Oprédélénnyh Gruppah. Doklady Akadémii Nauk SSSR, Vol. 147 , Pp. 805–808.Fridman A. A.. Degrees of Insolvability of the Word Problem in Finitely Defined Groups. English Translation of the Preceding by Walker Sue Ann. Soviet Mathematics, Vol. 3 No. 6 , Pp. 1733–1737.Clapham C. R. J.. Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility. Proceedings of the London Mathematical Society, Ser. 3 Vol. 14 , Pp. 633–676.Boone William W.. Finitely Presented Group Whose Word Problem has the Same Degree as That of an Arbitrarily Given Thue System . Proceedings of the National Academy of Sciences, Vol. 53 , Pp. 265–269.Boone William W.. Word Problems and Recursively Enumerable Degrees of Unsolvability. A First Paper on Thue Systems. Annals of Mathematics, Ser. 2 Vol. 83 , Pp. 520–571.Boone William W.. Word Problems and Recursively Enumerable Degrees of Unsolvability. A Sequel on Finitely Presented Groups. [REVIEW] Journal of Symbolic Logic 33 (2):296-297.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  14.  2
    C. T. Chong (1999). Computability, Enumerability, Unsolvability, Directions in Recursion Theory, Edited by Cooper SB, Slaman TA, and Wainer SS, London Mathematical Society Lecture Note Series, No. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, Vii+ 347 Pp. Harrington Leo and Soare Robert I., Dynamic Properties of Computably Enumerable Sets, Pp. 105–121. Herrmann Eberhard, On the∀∃-Theory of the Factor Lattice by the Major Subset Relation, Pp. 139–166. Lerman Manuel, Embeddings Into ... [REVIEW] Journal of Symbolic Logic 64 (3):1362-1365.
    Direct download  
     
    Export citation  
     
    My bibliography  
  15. C. T. Chong (1999). Computability, Enumerability, Unsolvability, Directions in Recursion Theory, Edited by Cooper S. B., Slaman T. A., and Wainer S. S., London Mathematical Society Lecture Note Series, No. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, Vii + 347 Pp.Harrington Leo and Soare Robert I., Dynamic Properties of Computably Enumerable Sets, Pp. 105–121.Herrmann Eberhard, On the ∀∃-Theory of the Factor Lattice by the Major Subset Relation, Pp. 139–166.Lerman Manuel, Embeddings Into the Recursively Enumerable Degrees, Pp. 185–204.Yi Xiaoding, Extension of Embeddings on the Recursively Enumerable Degrees Modulo the Cappable Degrees, Pp. 313–331.Nies André, Relativization of Structures Arising From Computability Theory. Pp. 219–232.Ambos-Spies Klaus, Resource-Bounded Genericity. Pp. 1–59.Downey Rod, Jockusch Carl G., and Stob Michael. Array Nonrecursive Degrees and Genericity, Pp. 93–104.Kumabe Masahiro, Degrees of Generic Sets, Pp. 167–183.Arslanov Marat M., Lemp. [REVIEW] Journal of Symbolic Logic 64 (3):1362-1365.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  16. Marian Boykan Pour-El (1963). Boone William W.. Partial Results Regarding Word Problems and Recursively Enumerable Degrees of Unsolvability. Bulletin of the American Mathematical Society, Vol. 68 , Pp. 616–623. [REVIEW] Journal of Symbolic Logic 28 (4):292.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  17. Gerald E. Sacks (1964). Shoenfield J. R.. On Degrees of Unsolvability. Annals of Mathematics, Second Series, Vol. 69 , Pp. 644–653.Shoenfield J. R.. An Uncountable Set of Incomparable Degrees. Proceedings of the American Mathematical Society, Vol. 11 , Pp. 61–62. [REVIEW] Journal of Symbolic Logic 29 (4):203-204.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  18. Leonard P. Sasso (1975). Shoenfield Joseph R.. Degrees of Unsolvability. North-Holland Mathematical Studies 2. North-Holland Publishing Company, Amsterdam-London, and American Elsevier Publishing Company, Inc., New York, 1971, VIII + 111 Pp. [REVIEW] Journal of Symbolic Logic 40 (3):452-453.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  19. W. E. Singletary (1969). Gladstone M. D.. Some Ways of Constructing a Propositional Calculus of Any Required Degree of Unsolvability. Transactions of the American Mathematical Society, Vol. 118 , Pp. 192–210. [REVIEW] Journal of Symbolic Logic 34 (3):505-506.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  20.  1
    A. H. Lachlan (1968). Distributive Initial Segments of the Degrees of Unsolvability. Mathematical Logic Quarterly 14 (30):457-472.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   16 citations  
  21.  13
    Richard A. Shore (1997). Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability. Archive for Mathematical Logic 36 (4-5):233-253.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  22.  40
    Jaroslav Peregrin, Diagonalization.
    It is a trivial fact that if we have a square table filled with numbers, we can always form a column which is not yet contained in the table. Despite its apparent triviality, this fact underlies the foundations of most of the path-breaking results of logic in the second half of the nineteenth and the first half of the twentieth century. We explain how this fact can be used to show that there are more sequences of natural numbers than (...)
    Direct download  
     
    Export citation  
     
    My bibliography  
  23.  11
    Xizhong Zheng (1994). The Rhombus Classes of Degrees of Unsolvability (I), The Jump Properties. Archive for Mathematical Logic 33 (1):1-12.
  24.  1
    J. C. Shepherdson (1965). Machine Configuration and Word Problems of Given Degree of Unsolvability. Mathematical Logic Quarterly 11 (2):149-175.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  25.  1
    S. B. Cooper (1972). Degrees of Unsolvability Complementary Between Recursively Enumerable Degrees, Part 1. Annals of Mathematical Logic 4 (1):31-73.
  26.  1
    Joanna Jedrzejowicz (1981). Undecidable Problems Associated with Combinatiorial Systems and Their One‐One Degrees of Unsolvability. Mathematical Logic Quarterly 27 (25‐30):453-462.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  27.  3
    Reuben Hersh (1998). Erratum. Philosophia Mathematica 6 (1):85-85.
    In my article on proof [Philosophia Mathematica (3) 5 (1997), 153—165], I suggested or intimated that computer proofs of mathematical theorems had been found only for relatively simple or trivial theorems. I am obligated to Martin Davis and R. S. Boyer for the information that this suggestion or intimation is incorrect. For instance, a machine proof of quadratic reciprocity was published by D. M. Russinoff in J. Automated Reasoning 8 (1992), 3–21. A machine proof of the unsolvability of the (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  28.  19
    S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) (1996). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press.
    The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped (...)
    Direct download  
     
    Export citation  
     
    My bibliography  
  29.  7
    Stephen G. Simpson (2007). Mass Problems and Almost Everywhere Domination. Mathematical Logic Quarterly 53 (4):483-492.
    We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b1, b2, and b3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let [MATHEMATICAL SCRIPT CAPITAL P]w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π01 subsets of 2ω. (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  30.  15
    Marcin Mostowski & Konrad Zdanowski (2004). Degrees of Logics with Henkin Quantifiers in Poor Vocabularies. Archive for Mathematical Logic 43 (5):691-702.
    We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  31.  14
    Rod Downey (1997). On the Universal Splitting Property. Mathematical Logic Quarterly 43 (3):311-320.
    We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  32.  5
    Carl Jockusch & Frank Stephan (1993). A Cohesive Set Which is Not High. Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   15 citations  
  33. S. B. Cooper (2001). On a Conjecture of Kleene and Post. Mathematical Logic Quarterly 47 (1):3-34.
    A proof is given that 0′ is definable in the structure of the degrees of unsolvability. This answers a long-standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  34.  16
    Stephen G. Simpson (1984). Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations? Journal of Symbolic Logic 49 (3):783-802.
    We investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA 0 whose principal axioms are ▵ 0 1 comprehension and Σ 0 1 induction. Our main result is that, over RCA 0 , the Cauchy/Peano Theorem is provably equivalent to weak Konig's lemma, i.e. the statement that every infinite {0, 1}-tree (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   18 citations  
  35.  45
    Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
    What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...)
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   8 citations