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

computabilityErshov hierarchyPost's programmerandomnessTuring invariance

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32) 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

• 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 emergence
• Computability and Randomness
• 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
• 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?)
• 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 program and incomplete recursively enumerable sets.
• Post's Programme for the Ershov Hierarchy
• 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^†
• 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
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Weak density and cupping in the d-r.e. degrees

Cited in

(2)

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

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)