Theses for Computation and Recursion on Concrete and Abstract Structures

DOI10.1007/978-3-319-22156-4_4zbMath1403.03004OpenAlexW2412938942MaRDI QIDQ4637218

Solomon Feferman

Publication date: 18 April 2018

Published in: Turing’s Revolution (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-22156-4_4

zbMATH Keywords

algorithmChurch's thesisrecursioncomputationChurch-Turing thesisconcrete structuresabstract structures

Mathematics Subject Classification ID

History of mathematics in the 20th century (01A60) History of mathematical logic and foundations (03-03) Turing machines and related notions (03D10) Abstract and axiomatic computability and recursion theory (03D75)

Related Items

What is the Church-Turing Thesis?, Why Turing’s Thesis Is Not a Thesis

Cites Work

• Theory of representations
• General recursive functions of natural numbers
• What Is an Algorithm?
• Computable functionals
• Recursive Functionals and Quantifiers of Finite Types I
• Only Two Letters: The Correspondence between Herbrand and Gödel
• The formal language of recursion
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Finite alogorithmic procedures and computation theories.
• Finite alogorithmic procedures and inductive definability.
• A new approach to abstract data types, I Informal development
• Algorithmic Procedures
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Axioms for Computability: Do They Allow a Proof of Church’s Thesis?
• On the definition of an algorithm
• Computability and Recursion
• Computability of Recursive Functions
• Sequential abstract-state machines capture sequential algorithms
• On Computable Numbers, with an Application to the Entscheidungsproblem
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES
• Recursive Predicates and Quantifiers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item