No creo que los grados de computabilidad fueran directamente relevantes para el tema de la conferencia de Gödel de 1946 porque no relativizan la computabilidad en el sentido relevante dependiente del lenguaje que enfatizó Gödel y Parsons después de él.

Stillwell da una explicación lúcida de la diferencia a este respecto entre la computabilidad de Turing (solubilidad, recursividad) y cosas como definibilidad y decidibilidad en su Emil Post and His Anticipation of Gödel and Turing, e indica que tanto Post como Gödel eran conscientes de ello:

" Como hemos visto, el punto de partida de Post fue el concepto de computación, que creía que podía formalizarse y someterse al argumento de la diagonal. La diagonalización genera problemas que son absolutamente irresolubles, en el sentido de que ningún cálculo puede resolverlos. A su vez, esto conduce a proposiciones relativamente indecidibles, por ejemplo, proposiciones de la forma $ n \ notin S_n $. Ningún sistema formal consistente $ F $ puede probar que todo es verdadero apuntalar posiciones de esta forma, por lo tanto, tales $ F $ deben fallar en probar alguna proposición verdadera $ n_o \ notin S_ {n_0} $. Pero esta proposición es relativamente indecidible, no absolutamente, porque $ F $ puede extenderse consistentemente agregándolo como axioma.

Gödel al principio no creía en problemas absolutamente irresolubles , porque no creía que la computación sea un concepto matemático. En cambio, demostró la existencia de proposiciones relativamente indecidibles directamente, construyendo una especie de argumento diagonal dentro de Principia Mathematica ".

¿Qué pasa con los" grados de computabilidad "? Turing insinúa de pasada en un artículo de 1939 donde introduce oráculos, pero la primera exposición clara es de hecho el artículo de Post de 1944. Sin embargo, no relativiza la recursividad a un lenguaje, sino que introduce una nueva noción de reducibilidad recursiva , que puede formalizarse en términos de consultar los oráculos de Turing. Como explica Post en su artículo:

" En ciertos momentos, el proceso determinado por la máquina plantea la pregunta de si hay un entero positivo en un conjunto enumerable recursivamente dado $ S_2 $ de enteros positivos, y que la máquina está construida de tal manera que fuera la respuesta correcta a esto. pregunta proporcionada en cada ocasión que surja, el proceso continuará automáticamente hasta su eventual conclusión correcta. Entonces podríamos decir que la máquina reduce efectivamente el problema de decisión de $ S_1 $ al de $ S_2 $. "

Pero no obtenemos una clase más grande de funciones recursivas extendiendo el formalismo, consultar un oráculo no es tal extensión. Una vez que entramos en la aritmética de Peano, el recursivo se corrige, se mueve a ZFC o no cambia nada, el no recursivo permanece no recursivo. Que algunos problemas sean reducibles recursivamente a otros problemas y no al revés establece una jerarquía, pero no se basa en una jerarquía de lenguajes. Los lenguajes más expresivos alteran la decidibilidad y la definibilidad, pero no hacen que sea computable incomputable, eso es absoluto.

¿Estaba Gödel al tanto del artículo de Post en 1946 (no es que importara por su elogio de Turing)? Computabilidad relativizada y computación interactiva de Turing-Post de Soare ofrece una descripción histórica detallada de los desarrollos desde 1936 hasta 1954. Desafortunadamente, no hay una respuesta directa. Post tenía la habilidad de ser pasado por alto. En cierto sentido, demostró el teorema de la incompletitud antes que Gödel y describió la máquina de Turing antes que Turing, pero obtuvo poco reconocimiento de ninguno de los dos (ver Stillwell). Hao Wong, el amigo y colega más cercano de Gödel que pasó incontables horas entrevistándolo, sugiere que Gödel también lo pasó por alto (a diferencia de Church, ni siquiera se lo menciona):

" A lo largo de los años, G habitualmente acreditó el artículo de AM Turing de 1936 como el trabajo definitivo en la captura del concepto intuitivo [de computabilidad], y no mencionó a Church ni a E. Post a este respecto. Debe haber sentido que Turing fue el único que dio argumentos persuasivos para demostrar la adecuación del concepto preciso ... En particular, probablemente había sido consciente de los argumentos ofrecidos por Church para su “tesis” y decidió que eran inadecuados. Está claro que G y Turing (1912-1954) se admiraban mucho el uno al otro ... "

Esto no sería particularmente sorprendente dado el tema de la conferencia de 1946 y el hecho de que antes " Post no intentó probar que su formalismo coincidiera con cualquier otro formalismo, como la recursividad general, sino que simplemente expresó la expectativa de que esto resultaría ser cierto ". Por otro lado, " fue sólo durante la siguiente fase de 1940 a 1954 que la notable influencia de Post se sintió plenamente. Cuando Turing dejó el tema de la teoría de la computabilidad pura en 1939, su manto cayó sobre los hombros de Post ". Ciertamente es probable que Gödel se diera cuenta del trabajo de Post y Kleene sobre la reducibilidad recursiva al menos en la década de 1950.