Turing oracle machines, online computing, and three displacements in computability theory

DOI10.1016/j.apal.2009.01.008zbMath1230.03073OpenAlexW2040069378MaRDI QIDQ1032637

Robert I. Soare

Publication date: 26 October 2009

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2009.01.008

zbMATH Keywords

relative computabilityChurch-Turing thesiscontinuous functionals on Cantor spacedatabase computingonline computingTuring oracle machines

Mathematics Subject Classification ID

History of mathematical logic and foundations (03-03) Turing machines and related notions (03D10) History of computer science (68-03)

Related Items

Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ Formalism and intuition in computability ⋮ The never-ending recursion ⋮ ``Viral Turing machines, computation from noise and combinatorial hierarchies ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Why Turing’s Thesis Is Not a Thesis ⋮ Concrete digital computation: what does it take for a physical system to compute? ⋮ Bounded Turing reductions and data processing inequalities for sequences ⋮ Rice and Rice-Shapiro Theorems for transfinite correction grammars

Cites Work

• Reflections on Church's thesis
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18--23, 2007. Proceedings.
• Church's thesis after 70 years
• The ibT degrees of computably enumerable sets are not dense
• On degrees of unsolvability
• General recursive functions of natural numbers
• The word problem in semi-groups with cancellation
• The upper semi-lattice of degrees of recursive unsolvability
• Turing Computability
• Alan Turing: Life and Legacy of a Great Thinker
• Algorithmic Randomness and Complexity
• Arithmetical Predicates and Function Quantifiers
• Hierarchies of number-theoretic predicates
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Recursive Functionals and Quantifiers of Finite Types I
• Computability Results Used in Differential Geometry
• Why Gödel didn't have church's thesis
• Reducibility and Completeness for Sets of Integers
• Some facts about Kurt Gödel
• The theory of recursive functions, approaching its centennial
• Origins of Recursive Function Theory
• An Early Program Proof by Alan Turing
• The Mathematical Work of S.C.Kleene
• Recursive Unsolvability of a problem of Thue
• Interactive Computation
• Incomputability after Alan Turing
• Computability and Incomputability
• Turing-Machine Computable Functionals of Finite Types II^†
• Trial and error predicates and the solution to a problem of Mostowski
• Computability and Recursion
• Computability Theory and Differential Geometry
• Recursive Functionals and Quantifiers of Finite Types II
• An Unsolvable Problem of Elementary Number Theory
• A note on the Entscheidungsproblem
• A note on recursive functions
• On notation for ordinal numbers
• On the Forms of the Predicates in the Theory of Constructive Ordinals
• Recursive Predicates and Quantifiers
• Formal Reductions of the General Combinatorial Decision Problem
• Recursively enumerable sets of positive integers and their decision problems
• Note on a conjecture of Skolem
• 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