Extending and interpreting Post's programme

DOI10.1016/J.APAL.2009.06.007MaRDI QIDQ636317zbMATH OpenOpenAlexFDO

Authors S. Barry Cooper

Publication date 26 August 2011

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.06.007

zbMATH Keywords

randomnesscomputabilityErshov hierarchyPost's programmeTuring invariance

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55) Applications of computability and recursion theory (03D80)

Recommendations

• The Extended Turing Model as Contextual Tool
• On the information carried by programs about the objects they compute
• Post's program and incomplete recursively enumerable sets.
• A glimpse into algorithmic information theory
• Incomputability emergent, and higher type computation

Cites work

• scientific article; zbMATH DE number 3117565 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 1955470 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• scientific article; zbMATH DE number 1405574 (Why is no real title available?)
• scientific article; zbMATH DE number 3264932 (Why is no real title available?)
• scientific article; zbMATH DE number 3317730 (Why is no real title available?)
• Algorithmic randomness and complexity.
• Arithmetical problems and recursively enumerable predicates
• Automorphisms of the lattice of recursively enumerable sets
• Bounding computably enumerable degrees in the Ershov hierarchy
• Calibrating Randomness
• Classical recursion theory. Vol. II
• Collected works of A. M. Turing. Mathematical logic. Edited by R. O. Gandy and C. E. M. Yates. Including prefaces by Solomon Feferman
• Computability and Randomness
• Computability and emergence
• Definability as hypercomputational effect
• Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
• Definable Encodings in the Computably Enumerable Sets
• Degrees of classes of RE sets
• Degrees of recursively enumerable sets which have no maximal supersets
• Isolation and the high/low hierarchy
• Limiting recursion
• Lowness properties and randomness
• Machines, Computations, and Universality
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On degrees of unsolvability
• On the Lattice of Recursively Enumerable Sets
• Post's Programme for the Ershov Hierarchy
• Post's program and incomplete recursively enumerable sets.
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Recursively enumerable sets of positive integers and their decision problems
• SOFSEM 2006: Theory and Practice of Computer Science
• Systems of Logic Based on Ordinals^†
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• The trouble with physics. The rise of string theory, the fall of a science and what comes next.
• The Δ₃⁰-automorphism method and noninvariant classes of degrees
• Theory and Applications of Models of Computation
• Trial and error predicates and the solution to a problem of Mostowski
• Weak density and cupping in the d-r.e. degrees

Cited in

(2)

• The Extended Turing Model as Contextual Tool
• Emergence as a computability-theoretic phenomenon

This page was built for publication: Extending and interpreting Post's programme

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