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 (10)

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

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