Who first discovered that some R.E. sets are not recursive?

According to the paper of Emil Post "Recursively Enumerable Sets of Positive Integers and Their Decision Problems" (1944):

Basic to the entire theory is the following result we must credit to Church, Rosser, Kleene, jointly.

THEOREM. There exists a recursively enumerable set of positive integers which is not recursive.

Cited are three papers all from 1936:

  • "An unsolvable problem of elementary number theory" (Church)
  • "General recursive functions of natural numbers" (Kleene)
  • "Extensions.of some theorems of Gödel and Church"(Rosser)

The Post paper and its three predecessors are all collected in Martin Davis's anthology The Undecidable.

Tags:

Logic

Computability

Math History

Related

Find polynomial whose root is sum of roots of other polynomials Trouble understanding Sum of Subspaces Proof of $\int_0^\infty \frac{x^{\alpha}dx}{1+2x\cos\beta +x^{2}}=\frac{\pi\sin (\alpha\beta)}{\sin (\alpha\pi)\sin \beta }$ Why does $S^n$ satisfy the local $n$-slice condition? (From Lee's Smooth Manifolds) How to solve equations involving modulus function of the type $|x+1| - |1-x|=2 $ and $ |x-1|=|x|+a$? Who are some blind or otherwise disabled mathematicians who have made important contributions to mathematics? Multivariable limit $\lim_ {{(x,y)} \to {(0,0)}} \frac{xy^2\ln\frac{|x|}{|y|}}{{(x^2+y^2)}^{\frac 12}}$ Prove that $\int_0^1\frac{\ln(1-x)\ln^2x}{x-1}dx=\frac{\pi^4}{180}$ Atiyah and Macdonald, Proposition 2.9 Is normal extension of normal extension always normal? Asymptotic behavior of $\sum\limits_{k=1}^n \frac{2^k}{k}$ Notation for all permutations of a set

Recent Posts