Computing degrees of unsolvability

On Computable Numbers, with an Application to the Entscheidungsproblem

Alan Turing · Proceedings of the London Mathematical Society · 1937 · 8.1K citations

Computing, Computer Science, Mathematics +10

Computability and Unsolvability.

Calvin C. Elgot, Martin Davis · Mathematical Tables and Other Aids to Computation · 1959 · 1K citations

Recursively enumerable sets of positive integers and their decision problems

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

Humanities, Computer Science, Mathematics +13

Recursive predicates and quantifiers

S. C. Kleene · Transactions of the American Mathematical Society · 1943 · 341 citations · Full text

Humanities, Mathematics, Algorithms +7

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

Natural Sciences, Mathematics, Combinatorics +6