Concepedia

Reducibility and Completeness for Sets of Integers

R. Friedberg, Hartley Rogers

Mathematical logic quarterly · 1959 · 127 citations · 8 references

DOI

Concepts

References

8

Recursively enumerable sets of positive integers and their decision problems

Emil L. Post · Bulletin of the American Mathematical Society · 1944 · 890 citations · Full text

, , +13

TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)

R. Friedberg · Proceedings of the National Academy of Sciences · 1957 · 298 citations · Full text

, , +6

The Upper Semi-Lattice of Degrees of Recursive Unsolvability

S. C. Kleene, Emil L. Post · Annals of Mathematics · 1954 · 276 citations

, , +13

On Degrees of Recursive Unsolvability

Clifford Spector · Annals of Mathematics · 1956 · 199 citations

, , +10

On completely recursively enumerable classes and their key arrays

H. G. Rice · Journal of Symbolic Logic · 1956 · 85 citations

, , +11