Formalism and intuition in computability

DOI10.1098/RSTA.2011.0335MaRDI QIDQ2941588zbMATH OpenOpenAlexWikidataFDO

Authors Robert I. Soare

Publication date 21 August 2015

Published in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1098/rsta.2011.0335

zbMATH Keywords

computability theoryoracle machinePostrelative computabilityTuring degreeTuring machines

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) Recursive functions and relations, subrecursive hierarchies (03D20) Other Turing degree structures (03D28)

Recommendations

• Gödel's reception of Turing's model of computability: the shift of perception in 1934
• The developments of the concept of machine computability from 1936 to the 1960s
• Computability and Incomputability
• Computability and Recursion
• Conceptual Confluence in 1936: Post and Turing

Cites work

• \(\lambda\)-definability and recursiveness
• A recursively enumerable degree which will not split over all lesser ones
• Computability and Recursion
• Formal Reductions of the General Combinatorial Decision Problem
• General recursive functions of natural numbers
• scientific article; zbMATH DE number 3860368 (Why is no real title available?)
• scientific article; zbMATH DE number 193560 (Why is no real title available?)
• scientific article; zbMATH DE number 5251035 (Why is no real title available?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On notation for ordinal numbers
• On some games which are relevant to the theory of recursively enumerable sets
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Reflections on Church's thesis
• Systems of Logic Based on Ordinals^†
• The upper semi-lattice of degrees of recursive unsolvability
• Turing computability. Theory and applications
• Turing oracle machines, online computing, and three displacements in computability theory
• Why Gödel didn't have church's thesis
• Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Cited in

(5)

• The never-ending recursion
• Gödel's reception of Turing's model of computability: the shift of perception in 1934
• The foundations of computation, physics and mentality: the Turing legacy
• Why Turing’s Thesis Is Not a Thesis
• A personal account of Turing's imprint on the development of computer science

This page was built for publication: Formalism and intuition in computability

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