¿Cómo se verían los teoremas de incompletitud de Godel/Rosser desde un punto de vista de computabilidad?
A menudo las personas presentan los teoremas de incompletitud como relacionados con la aritmética, pero algunas personas como Scott Aaronson han expresado la opinión de que el núcleo del fenómeno de incompletitud es la no computabilidad, y que incluso la numeración de Godel (con el -lema asociado) no es realmente crucial. Entonces, ¿existen pruebas y discusiones de los teoremas de incompletitud y fenómenos relacionados puramente basados en computabilidad?
También me interesa saber si hay un texto de referencia que contenga este tipo de discusión en una presentación rigurosa (no publicaciones de blog).
En mi respuesta a continuación, proporciono tanto afirmaciones basadas en computabilidad como pruebas de los teoremas de incompletitud generalizados, y algunas referencias bibliográficas. Me motivó escribir esto porque las preguntas autorespondidas de buena calidad son alentadas tanto por <a href="https://math.stackexchange.com/help/answering">las pautas de StackExchange</a> como por el <a href="https://math.meta.stackexchange.com/a/21719/21820">consenso de la comunidad</a>.
