Switch to: Citations

Add references

You must login to add references.
  1. Choiceless Polynomial Time, Counting and the Cai–Fürer–Immerman Graphs.Anuj Dawar, David Richerby & Benjamin Rossman - 2008 - Annals of Pure and Applied Logic 152 (1):31-50.
    We consider Choiceless Polynomial Time , a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting from image. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • The Prospects for Mathematical Logic in the Twenty-First Century.Samuel R. Buss, Alexander S. Kechris, Anand Pillay & Richard A. Shore - 2001 - Bulletin of Symbolic Logic 7 (2):169-196.
    The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
  • Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic.Richard Zach - 1999 - Bulletin of Symbolic Logic 5 (3):331-366.
    Some of the most important developments of symbolic logic took place in the 1920s. Foremost among them are the distinction between syntax and semantics and the formulation of questions of completeness and decidability of logical systems. David Hilbert and his students played a very important part in these developments. Their contributions can be traced to unpublished lecture notes and other manuscripts by Hilbert and Bernays dating to the period 1917-1923. The aim of this paper is to describe these results, focussing (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   31 citations  
  • Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
    Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turing machines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, we must correlate these syntactic (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  • Proving Church's Thesis.Robert Black - 2000 - Philosophia Mathematica 8 (3):244--58.
    Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Church's Thesis: Prelude to a Proof.Janet Folina - 1998 - Philosophia Mathematica 6 (3):302-323.
  • An Abstract Model For Parallel Computations: Gandy’s Thesis.Wilfried Sieg & John Byrnes - 1999 - The Monist 82 (1):150-164.
    Wilfried Sieg and John Byrnes. AnModel for Parallel Computation: Gandy's Thesis.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  • An Abstract Model For Parallel Computations.John Byrnes - 1999 - The Monist 82 (1):150-164.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  • Second Thoughts About Church's Thesis and Mathematical Proofs.Elliott Mendelson - 1990 - Journal of Philosophy 87 (5):225.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  • The Concept of Truth in Formalized Languages.Alfred Tarski - 1936 - In A. Tarski (ed.), Logic, Semantics, Metamathematics. Oxford University Press. pp. 152--278.
  • Finite Combinatory Processes—Formulation.Emil L. Post - 1936 - Journal of Symbolic Logic 1 (3):103-105.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   36 citations  
  • Computability and Λ-Definability.A. M. Turing - 1937 - Journal of Symbolic Logic 2 (4):153-163.
  • Understanding Church's Thesis.Stewart Shapiro - 1981 - Journal of Philosophical Logic 10 (3):353--65.
  • Reflections on Church's Thesis.Stephen C. Kleene - 1987 - Notre Dame Journal of Formal Logic 28 (4):490-498.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  • Acceptable Notation.Stewart Shapiro - 1982 - Notre Dame Journal of Formal Logic 23 (1):14-20.
  • An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
  • Effective Computation by Humans and Machines.Shagrir Oron - 2002 - Minds and Machines 12 (2):221-240.
    There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument (...)
    Direct download (15 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • The Impact of the Lambda Calculus in Logic and Computer Science.Henk Barendregt - 1997 - Bulletin of Symbolic Logic 3 (2):181-215.
    One of the most important contributions of A. Church to logic is his invention of the lambda calculus. We present the genesis of this theory and its two major areas of application: the representation of computations and the resulting functional programming languages on the one hand and the representation of reasoning and the resulting systems of computer mathematics on the other hand.
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • Limiting Recursion.E. Mark Gold - 1965 - Journal of Symbolic Logic 30 (1):28-48.
    A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   50 citations  
  • Towards a General Theory of Computability.Richard Montague - 1960 - Synthese 12 (4):429 - 438.
  • What is an Algorithm?Yiannis Moschovakis - 2001 - In Mathematics Unlimited --- 2001 and beyond.
     
    Export citation  
     
    Bookmark   18 citations  
  • Trial and Error Predicates and the Solution to a Problem of Mostowski.Hilary Putnam - 1965 - Journal of Symbolic Logic 30 (1):49-57.
  • When Are Two Algorithms the Same?Andreas Blass, Nachum Dershowitz & Yuri Gurevich - 2009 - Bulletin of Symbolic Logic 15 (2):145-168.
    People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • An Informal Exposition of Proofs of Gödel's Theorems and Church's Theorem.Barkley Rosser - 1939 - Journal of Symbolic Logic 4 (2):53-60.
  • Finite Combinatory Processes—Formulation.Emil L. Post - 1936 - Journal of Symbolic Logic 1 (3):103-105.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   30 citations  
  • A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
  • A Notion of Effectiveness in Arbitrary Structures.W. M. Lambert - 1968 - Journal of Symbolic Logic 33 (4):577-602.
  • Glossary.[author unknown] - 1995 - Journal of Moral Education 24 (3):353-356.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Comparing Computational Power.Udi Boker & Nachum Dershowitz - 2006 - Logic Journal of the IGPL 14 (5):633-647.
    It is common practice to compare the computational power of different models of computation. For example, the recursive functions are strictly more powerful than the primitive recursive functions, because the latter are a proper subset of the former . Side-by-side with this “containment” method of measuring power, it is also standard to base comparisons on “simulation”. For example, one says that the lambda calculus is as powerful—computationally speaking—as the partial recursive functions, because the lambda calculus can simulate all partial recursive (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation