¿Quién primero descubrió que algunos conjuntos R.E. no son recursivos?

Question

¿Quién primero descubrió que algunos conjuntos de recursivamente enumerable no recursivas, o equivalente que algunos sistemas semidecidable son indecidibles? ¿Y en qué contexto? ¿Fue la primera formulación de esta idea expresada en términos de funciones recursivas parciales? ¿O algo más?

Answer 1

Emil Post, en su artículo "recursivamente Enumerable conjuntos de enteros positivos y sus problemas de decisión" (1944). Esto se puede encontrar en el libro "el Undecidable: documentos básicos sobre las proposiciones indecidibles, problemas irresolubles y funciones computables", ed. Martin Davis, pp. 305-37.