A Natural Axiomatization of Computability and Proof of Church's Thesis

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Bulletin of Symbolic Logic

• Publication date

  2008-09-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.2178/bsl/1231081370
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computability, complexity, and languages - fundamentals of theoretical computer science

  2014cited by this paper
• An ASM-Characterization of a Class of Distributed Algorithms

  2009cited by this paper
• When are Two Algorithms the Same?

  2008cited by this paper
• Recursion Theory I

  2008cited by this paper
• The Church-Turing Thesis over Arbitrary Domains

  2008cited by this paper
• Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday

  2008cited by this paper
• Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract)

  2008cited by this paper
• Why Sets?

  2008cited by this paper
• Church's Thesis After 70 Years

  2007cited by this paper
• Church's Thesis and the Conceptual Analysis of Computability

  2007cited by this paper
• Ordinary interactive small-step algorithms, II

  2007cited by this paper
• Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem

  2007cited by this paper
• Interactive Small-Step Algorithms I: Axiomatization

  2007cited by this paper
• New Computational Paradigms: Changing Conceptions of What is Computable

  2007cited by this paper
• Ordinary interactive small-step algorithms, I

  2007cited by this paper
• Proving Church's Thesis

  2007cited by this paper
• On the Church-Turing thesis

  2006cited by this paper
• On the Impossibility of Proving the “Hard-Half” of Church’s Thesis

  2006cited by this paper
• Abstract state machines capture parallel algorithms: Correction and extension

  2006cited by this paper
• Distributed Abstract State Machines and Their Expressive Power

  2006cited by this paper
• Gödel on Computability

  2006cited by this paper
• Abstract Effective Models

  2006cited by this paper
• MATHEMATICAL LOGIC: WHAT HAS IT DONE FOR THE PHILOSOPHY OF MATHEMATICS?

  2005cited by this paper
• Comparing Computational Power

  2005cited by this paper
• The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma

  2004cited by this paper
• Current Trends in Theoretical Computer Science: The Challenge of the New Century

  2004cited by this paper
• Constructivity in Mathematics

  2004cited by this paper
• A sequent calculus for nominal logic

  2004cited by this paper
• ENUMERABLE SETS ARE DIOPHANTINE

  2003cited by this paper
• Abstract state machines capture parallel algorithms

  2003cited by this paper
• Algorithms: A Quest for Absolute Definitions

  2003cited by this paper
• On Gurevich's theorem on sequential algorithms

  2003cited by this paper
• Stanford Encyclopedia of Philosophy: a dynamic reference work

  2003cited by this paper
• The Origins and the Development of the ASM Method for High Level System Design and Analysis

  2002cited by this paper
• Effective Computation by Humans and Machines

  2002cited by this paper
• Java and the Java Virtual Machine: Definition, Verification, Validation

  2001cited by this paper
• The nine chapters on the mathematical art: companion and commentary

  2001cited by this paper
• Java and the Java Virtual Machine

  2001cited by this paper
• Mathematics unlimited - 2001 and beyond

  2001cited by this paper
• The Prospects for Mathematical Logic in the Twenty-First Century

  2001cited by this paper
• Computational neuroscience: more math is needed to understand the human brain

  2001cited by this paper
• Calculations by Man and Machine: Mathematical Presentation

  2000cited by this paper
• From the church-turing thesis to the first-order algorithm theorem

  2000cited by this paper
• Sequential abstract-state machines capture sequential algorithms

  2000cited by this paper
• Calculations by Man and Machine: Conceptual Analysis

  2000cited by this paper
• An abstract model for parallel computations : Gandy's thesis

  1999cited by this paper
• Completeness Before Post: Bernays, Hilbert, and the Development of Propositional Logic

  1999cited by this paper
• Church's Thesis: Prelude to a Proof

  1998influential reference
• Universal Turing Machine

  1998cited by this paper
• The Impact of the Lambda Calculus in Logic and Computer Science

  1997cited by this paper
• Step by Recursive Step: Church's Analysis of Effective Calculability

  1997cited by this paper
• K-graph machines : generalizing Turing's machines and arguments

  1996cited by this paper
• The universal turing machine: a half-century survey

  1996cited by this paper
• Gödel '96 Logical Foundations of Mathematics, Computer Science and Physics Kurt GÖdel's Legacy

  1996cited by this paper
• Computability and Recursion

  1996influential reference
• Specification and validation methods

  1995cited by this paper
• Mathematics and mind

  1994cited by this paper
• Solvability, provability, definability: the collected works of Emil L. Post

  1994cited by this paper
• Generalizing Turing's Machine and Arguments

  1994cited by this paper
• Algorithms: Main Ideas and Applications

  1993cited by this paper
• The Universal Turing Machine: A Half-Century Survey

  1992cited by this paper
• The Semantics of the C Programming Language

  1992cited by this paper
• Mechanical Procedures and Mathematical Experience

  1991cited by this paper
• Second Thoughts about Church's Thesis and Mathematical Proofs

  1990cited by this paper
• The theory of functions and sets of natural numbers

  1989cited by this paper
• ALGORITHM AND PROGRAM

  1988cited by this paper
• Turing's analysis of computability, and major applications of it

  1988cited by this paper
• The confluence of ideas in 1936

  1988cited by this paper
• Algebraic Specifications of Computable and Semicomputable Data Types

  1987cited by this paper
• Algebraic specifications of computable and semi-computable data structures

  1987cited by this paper
• Reflections on Church's thesis

  1987cited by this paper
• Kurt Gödel : collected works

  1986cited by this paper
• Mathematical logic

  1985cited by this paper
• The art of computer programming

  1983cited by this paper
• JSL volume 49 issue 4 Cover and Back matter and Errata

  1983cited by this paper
• Why Gödel Didn't Have Church's Thesis

  1982cited by this paper
• Highlights of the History of the Lambda-Calculus

  1982cited by this paper
• Acceptable notation

  1982cited by this paper
• Origins of Recursive Function Theory

  1981cited by this paper
• Understanding Church's thesis

  1981cited by this paper
• The Kleene Symposium

  1980cited by this paper
• Mechanism, Mentalism, and Metamathematics. An Essay on Finitism.

  1980cited by this paper
• Church's Thesis and Principles for Mechanisms

  1980cited by this paper
• Storage Modification Machines

  1979cited by this paper
• The optimal approach to recursive programs

  1977cited by this paper
• FROM MATHEMATICS TO PHILOSOPHY

  1974cited by this paper
• A Two Counter Machine Cannot Calculate 2N

  1972cited by this paper
• Theory of Recursive Functions and Effective Computability

  1969cited by this paper
• A notion of effectiveness in arbitrary structures

  1969cited by this paper
• Mathematical Logic

  1968cited by this paper
• Bertrand Russell: Philosopher of the Century

  1967cited by this paper
• Mathematical logic

  1967cited by this paper
• Computation: Finite and Infinite Machines

  1967cited by this paper
• Trial and error predicates and the solution to a problem of Mostowski

  1965cited by this paper
• Limiting recursion

  1965cited by this paper
• Towards a general theory of computability

  1960cited by this paper
• Computable algebra, general theory and theory of computable fields.

  1960cited by this paper
• Effective procedures in field theory

  1956cited by this paper
• Turing A. M.. Solvable and unsolvable problems. Science news (Penguin books, Melbourne–London–Baltimore), no. 31 (1954), pp. 7–23.

  1955cited by this paper
• Introduction to Metamathematics

  1952cited by this paper

• Basic interactive algorithms: Preview

  2025cites this paper
• Semi-mathematical statements

  2025cites this paper
• A Categorical Model of General Consciousness

  2025cites this paper
• Relative Constructibility via Generalised Sequential Algorithms

  2024cites this paper
• The open texture of ‘algorithm’ in legal language

  2024cites this paper
• Exact Exploration

  2024cites this paper
• The Decision Problem for Effective Procedures

  2023cites this paper
• Effective Procedures

  2023cites this paper
• Semantics of quantum programming languages: Classical control, quantum control

  2022cites this paper
• Elementary recursive algorithms

  2021cites this paper
• Reversify any sequential algorithm

  2021cites this paper
• Explication as a Three-Step Procedure: the case of the Church-Turing Thesis

  2021cites this paper
• What is the Church-Turing Thesis?

  2020cites this paper
• T he L ogic in C omputer S cience C olumn

  2020influential citation
• Insights in how computer science can be a science

  2020cites this paper
• Axiomatization, Computability and Stability for Discrete Event Time Algorithms

  2020influential citation
• TOWARDS AN EVALUATION OF THE NORMALISATION THESIS ON IDENTITY OF PROOFS: THE CASE OF CHURCH-TURING THESIS AS TOUCHSTONE

  2020cites this paper
• The Foundations of Computability Theory

  2020cites this paper
• A Theory of Natural Universal Computation Through RNA

  2020cites this paper
• An RNA-Based Theory of Natural Universal Computation.

  2020cites this paper
• Theoretical Computer Science: Computability, Decidability and Logic

  2020cites this paper
• Means-fit effectivity

  2020influential citation
• Unconstrained Church-Turing thesis cannot possibly be true

  2019cites this paper
• THE CHURCH THESIS, ITS PROOF, AND THE NOTION OF STABILITY AND STABILIZATION FOR ANALOG ALGORITHMS

  2019influential citation
• Computability and Stability for Hybrid Algorithms

  2019cites this paper
• Computing, Modelling, and Scientific Practice: Foundational Analyses and Limitations

  2018cites this paper
• Sailing Routes in the World of Computation

  2018cites this paper
• The Church-Turing thesis

  2018influential citation
• A Survey on Analog Models of Computation

  2018cites this paper
• Abstract Recursion and Intrinsic Complexity

  2018cites this paper
• What Is the Concept of Computation?

  2018cites this paper
• What is a Physical Realization of a Computational System

  2017cites this paper
• What is an Algorithm? (Revised)

  2017influential citation
• Is there any Real Substance to the Claims for a 'New Computationalism'?

  2017cites this paper
• On the parallel computation thesis

  2016cites this paper
• A Refutation of the Church-Turing Thesis According to Some Interpretation of What the Thesis Says

  2016cites this paper
• Honest Computability and Complexity

  2016cites this paper
• Defining Effectiveness Using Finite Sets A Study on Computability

  2016cites this paper
• Chapter 6 Honest Computability and Complexity

  2016cites this paper
• Finiteness and Computation in Toposes

  2016cites this paper
• Axiomatizing Analog Algorithms

  2016cites this paper
• Semantics-to-Syntax Analyses of Algorithms

  2015cites this paper
• Continuous models of computation: from computability to complexity. (Modèles de calculs à temps continu: de la calculabilité à la complexité)

  2015cites this paper
• HONEST COMPUTABILITY AND COMPLEXITY UDI BOKER AND NACHUM DERSHOWITZ Draft of March 31 , 2015 Goldstein : And what causes you to say that ? Davis : Honesty

  2015cites this paper
• SEMANTICAL MUTATION, ALGORITHMS AND PROGRAMS

  2015cites this paper
• Generalized sorting problems: a symbolic view on reversible algorithms

  2015cites this paper
• Conceptual Confluence in 1936: Post and Turing

  2015cites this paper
• Should Computability Be Epistemic? a Logical and Physical Point of View

  2015cites this paper
• Cellular Automata are Generic

  2015cites this paper
• Why Turing’s Thesis Is Not a Thesis

  2015cites this paper
• Theses for Computation and Recursion on Concrete and Abstract Structures

  2015cites this paper
• Can everything be computed? - On the Solvability Complexity Index and Towers of Algorithms

  2015cites this paper
• Computation as Information Processing

  2014cites this paper
• On generic computational models

  2014influential citation
• An Analysis of Artificial Intelligence in Machines with Turing Machine

  2014cites this paper
• The Invariance Thesis

  2014cites this paper
• Generic Parallel Algorithms

  2014cites this paper
• Philosophy and Computers

  2013cites this paper
• Crowd computing: a survey

  2013cites this paper
• RAM Complexity is Optimal

  2013cites this paper
• Verifying Time Complexity of Turing Machines

  2013cites this paper
• Application-Sensitive Access Control Evaluation Using Parameterized Expressiveness

  2013cites this paper
• On the Optimality of RAM Complexity

  2013cites this paper
• Integrating high-level requirements in optimization problems: theory and applications

  2013cites this paper
• Crowd Labeling: a survey

  2013cites this paper
• Towards a Church-Turing-Thesis for Infinitary Computations

  2013cites this paper
• Axioms for Computability: Do They Allow a Proof of Church’s Thesis?

  2012cites this paper
• Information Processing as an Account of Concrete Digital Computation

  2012cites this paper
• What Is Nature-Like Computation? A Behavioural Approach and a Notion of Programmability

  2012cites this paper
• How the World Computes

  2012influential citation
• Copeland and Proudfoot on computability

  2012cites this paper
• What Is an Algorithm?

  2012cites this paper
• Combinatorial-State Automata and Models of Computation

  2012cites this paper
• A tese de Church-Turing

  2012cites this paper
• A tese de Church–Turing

  2012cites this paper
• Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul

  2012cites this paper
• Application-Sensitive Access Control Evaluation : Logical Foundations ( Extended Version )

  2012cites this paper
• Nature-Like Computation and a Measure of Programmability 1

  2012cites this paper
• RAM is as Good as it Gets

  2012cites this paper
• Random-Access Machines and the Extended Church-Turing Thesis

  2012cites this paper
• Unconventional Algorithms: Complementarity of Axiomatics and Construction

  2012cites this paper
• Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory

  2012cites this paper
• Towards an Axiomatization of Simple Analog Algorithms

  2012cites this paper
• Foundations of Analog Algorithms

  2012cites this paper
• Foundational Analyses of Computation

  2012cites this paper
• Honest universality

  2012cites this paper
• Functionals Using Bounded Information and the Dynamics of Algorithms

  2012cites this paper
• A Formalization and Proof of the Extended Church-Turing Thesis -Extended Abstract-

  2012cites this paper
• Axiomatic Tools versus Constructive approach to Unconventional Algorithms

  2012cites this paper
• The Generic Model of Computation

  2012influential citation
• The Physical Church-Turing Thesis and the Principles of Quantum Theory

  2011cites this paper
• An executable theory of multi-agent systems refinement

  2011cites this paper
• Concept Formation in Mathematics

  2011cites this paper
• Beyond Formal Structure: A Mechanistic Perspective on Computation and Implementation

  2011cites this paper
• HORNER’S RULE IS OPTIMAL FOR POLYNOMIAL NULLITY

  2011influential citation
• Persistent queries in the behavioral theory of algorithms

  2011cites this paper
• In Defense of the Unprovability of the Church-Turing Thesis

  2010cites this paper
• In Defense of the Unprovability of the Church-Turing Thesis

  2010cites this paper
• Abstract State Machines : A Generic Model of Computation

  2010cites this paper
• Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality

  2010cites this paper