Completeness, the Recursion Theorem, and Effectively Simple Sets

DOI10.2307/2036264MaRDI QIDQ5619820zbMATH OpenOpenAlexFDO

Authors Donald A. Martin

Publication date 1966

Full work available at URL https://doi.org/10.2307/2036264

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Recursively (computably) enumerable sets and degrees (03D25)

Cites work

• A Simple Set Which is Not Effectively Simple
• A theorem on hyperhypersimple sets
• A Theorem on Hypersimple Sets
• Creative sets
• Effectively Simple Sets
• On a Class of Complete Simple Sets
• Quasicreative Sets
• Recursively enumerable sets of positive integers and their decision problems

Cited in

(11)

• An excursion to the Kolmogorov random strings
• Effectively hyperimmune sets and majorants
• On effectively hypersimple sets
• What can be efficiently reduced to the Kolmogorov-random strings?
• Effective bi-immunity and randomness
• Recursively enumerable sets and degrees
• Generalized cohesiveness
• Complete Recursively Enumerable Sets
• Semirecursive Sets and Positive Reducibility
• Degrees of sets having no subsets of higher m- and t t-degree
• Constructivity conditions on immune sets

This page was built for publication: Completeness, the Recursion Theorem, and Effectively Simple Sets

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