A Natural Axiomatization of Computability and Proof of Church's Thesis
From MaRDI portal
Publication:3616433
DOI10.2178/bsl/1231081370zbMath1167.03027OpenAlexW2121136774MaRDI QIDQ3616433
Nachum Dershowitz, Yuri Gurevich
Publication date: 25 March 2009
Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/bsl/1231081370
algorithmsChurch's thesiscomputable functionsabstract state machinesencodingsrecursivenesseffective computationTuring's thesis
Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)
Related Items
What Is an Algorithm?, What is the Church-Turing Thesis?, Axiomatizing Analog Algorithms, Semantics of quantum programming languages: Classical control, quantum control, Honest universality, An RNA-based theory of natural universal computation, Unconventional algorithms: complementarity of axiomatics and construction, The decision problem for effective procedures, Unnamed Item, Unnamed Item, Conceptual Confluence in 1936: Post and Turing, Theses for Computation and Recursion on Concrete and Abstract Structures, Semantics-to-Syntax Analyses of Algorithms, Why Turing’s Thesis Is Not a Thesis, Honest Computability and Complexity, Defining effectiveness using finite sets. A study on computability, Three Paths to Effectiveness, ASMs and Operational Algorithmic Completeness of Lambda Calculus, Is there any real substance to the claims for a ``new computationalism?, The Church-Turing Thesis over Arbitrary Domains, A Survey on Analog Models of Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algebraic specifications of computable and semicomputable data types
- Reflections on Church's thesis
- Acceptable notation
- Conservative logic
- On Gurevich's theorem on sequential algorithms
- Church's thesis and the conceptual analysis of computability
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Church's thesis after 70 years
- Proving Church's Thesis
- The Prospects for Mathematical Logic in the Twenty-First Century
- Second Thoughts about Church's Thesis and Mathematical Proofs
- Effective procedures in field theory
- Comparing Computational Power
- Why Gödel didn't have church's thesis
- Storage Modification Machines
- The optimal approach to recursive programs
- Church's Thesis: Prelude to a Proof
- Step by Recursive Step: Church's Analysis of Effective Calculability
- Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic
- Abstract state machines capture parallel algorithms
- Ordinary interactive small-step algorithms, I
- Church Without Dogma: Axioms for Computability
- Why Sets?
- The Church-Turing Thesis over Arbitrary Domains
- Trial and error predicates and the solution to a problem of Mostowski
- Limiting recursion
- Sequential abstract-state machines capture sequential algorithms
- An Unsolvable Problem of Elementary Number Theory
- A note on the Entscheidungsproblem
- Finite combinatory processes—formulation
- Computability and λ-definability
- An informal exposition of proofs of Gödel's theorems and Church's theorem
- Formal Reductions of the General Combinatorial Decision Problem
