Completeness, the Recursion Theorem, and Effectively Simple Sets

DOI10.2307/2036264zbMath0216.29003OpenAlexW4237616187MaRDI QIDQ5619820

Donald A. Martin

Publication date: 1966

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

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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