What is the Church-Turing Thesis?

DOI10.1007/978-3-030-77799-9_9OpenAlexW4296129219MaRDI QIDQ5055286FDOQ5055286

Authors: Udi Boker, Nachum Dershowitz 

Publication date: 13 December 2022

Published in: Axiomatic Thinking II (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-77799-9_9

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) History of mathematical logic and foundations (03-03)

Cites Work

• Quantum theory, the Church–Turing principle and the universal quantum computer
• Outline of a Theory of Truth
• Title not available (Why is that?)
• Non-Turing computations via Malament--Hogarth space-times
• Introduction to mathematical logic
• Hypercomputation
• Computational Complexity of Probabilistic Turing Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trial and error predicates and the solution to a problem of Mostowski
• Sequential abstract-state machines capture sequential algorithms
• Title not available (Why is that?)
• Quantum algorithm for Hilbert's tenth problem
• Title not available (Why is that?)
• Computability and realizability for interactive computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Limiting recursion
• Title not available (Why is that?)
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Automata Studies. (AM-34)
• Interactive Computation
• Title not available (Why is that?)
• Machines, Computations, and Universality
• What is an algorithm?
• Title not available (Why is that?)
• Church Without Dogma: Axioms for Computability
• Title not available (Why is that?)
• The physical Church-Turing thesis: modest or bold?
• Why was Wantzel overlooked for a century? The changing importance of an impossibility result
• Title not available (Why is that?)
• The Impact of the Lambda Calculus in Logic and Computer Science
• Title not available (Why is that?)
• Hypercomputation and the Physical Church‐Turing Thesis
• Why Gödel didn't have church's thesis
• Title not available (Why is that?)
• Locality and information transfer in quantum operations
• Title not available (Why is that?)
• On the Definition of Computable Function of a Real Variable
• Finite combinatory processes—formulation
• Title not available (Why is that?)
• The Church-Turing Thesis over Arbitrary Domains
• Title not available (Why is that?)
• The computable kernel of abstract state machines
• The influence of domain interpretations on computational models
• Acceptable notation
• Church's thesis and the conceptual analysis of computability
• A hypercomputational alien
• The Church-Turing thesis: Still valid after all these years?
• Three counterexamples refuting Kieu's plan for ``quantum adiabatic hypercomputation; and some uncomputable quantum mechanical tasks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Origins of Recursive Function Theory
• New Computational Paradigms
• Title not available (Why is that?)
• \(\lambda\)-definability and recursiveness
• Title not available (Why is that?)
• Second thoughts about Church's thesis and mathematical proofs
• A foundation of finite mathematics
• Why Gödel's theorem cannot refute computationalism
• Title not available (Why is that?)
• Superminds. People harness hypercomputation, and more
• Title not available (Why is that?)
• On the mechanization of straightedge and compass constructions
• Church's Thesis: Prelude to a Proof
• Step by Recursive Step: Church's Analysis of Effective Calculability
• Axioms for computability: do they allow a proof of Church's thesis?
• Title not available (Why is that?)
• An Interview with Herbert Robbins
• An impossible program
• On some recent criticism of Church's thesis
• Title not available (Why is that?)
• Kalmár's argument against the plausibility of Church's thesis
• The physical Church-Turing thesis and the principles of quantum theory
• Representations of natural numbers and computability of various functions
• Is there a ``Hilbert thesis?
• Physical constraints on hypercomputation
• Logical Approaches to Computational Barriers
• A new Gödelian argument for hypercomputing minds based on the busy beaver problem
• Comparing Computational Power
• Proving Church's thesis
• Title not available (Why is that?)
• Abstract effective models
• Axiomatizing analog algorithms
• Title not available (Why is that?)
• Three paths to effectiveness
• True Random Number Generators
• The universal computer. The road from Leibniz to Turing
• Theses for computation and recursion on concrete and abstract structures
• Proving Things About the Informal
• Unconstrained Church-Turing thesis cannot possibly be true
• The Four Sons of Penrose
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• Hilbert’s Axiomatisches Denken
• Title not available (Why is that?)

This page was built for publication: What is the Church-Turing Thesis?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5055286)