Se puede demostrar que dos modelos informáticos están completos si cada uno puede codificar un simulador universal para el otro. Se puede demostrar que dos lógicas están completas si una codificación de las reglas de inferencias (y tal vez los axiomas si están presentes) de cada uno se muestra como teorema del otro. En computabilidad, esto ha llevado a una idea natural de la integridad de Turing y la Tesis de Turing de la Iglesia. Sin embargo, no he visto dónde la completitud lógica ha llevado a una idea inducida naturalmente de una integridad total de calidad similar.
Dado que Provability y Computability están tan estrechamente relacionadas, creo que no es demasiado considerar que podría haber un concepto en lógica que sea un doble natural para la integridad de Turing. Especulativamente, algo así como: hay un teorema "verdadero" que no es demostrable en una lógica si y solo si hay una función computable que no es describible por un modelo informático. Mi pregunta es, ¿alguien ha estudiado esto? Una referencia o algunas palabras clave serían útiles.
Por "verdadero" y "computable" en el párrafo anterior me refiero a las ideas intuitivas pero en última instancia indefinibles. Por ejemplo, alguien podría mostrar que la finitud de las secuencias de Goodstein es "verdadera" pero no demostrable en la aritmética de Peano sin definir completamente el concepto de "verdadera". Del mismo modo, por diagonalización se puede demostrar que hay funciones computables que no son primitivas recursivas sin definir realmente el concepto de computable. Me preguntaba, aunque en última instancia tienden a ser conceptos empíricos, tal vez los conceptos podrían estar relacionados entre sí lo suficientemente bien como para relacionar los conceptos de integridad.
fuente
Respuestas:
No estoy seguro de por qué dice "verdadero" en última instancia es indefinible, ya que existe una definición precisa de lo que significa que una fórmula de primer orden sea verdadera .
Lo que es único en el caso de la computabilidad, es que para cualquier definición (tan descabellada como sus sueños) de un "modelo computacional", finalmente puede asociarlo con un conjunto de funciones (las funciones que puede calcular). Por lo tanto, naturalmente puede comparar diferentes modelos, y al arreglar uno (basado en alguna justificación empírica como "es una buena representación de la computación en el mundo real") puede llamar a cualquier otro modelo completo si computa exactamente el mismo conjunto de funciones
Sin embargo, ¿cómo se comparan las diferentes lógicas? Parece que no hay una propiedad natural que pueda asociar a una lógica arbitraria, y usarla para compararla con otros sistemas. Quizás pueda arreglar la lógica, por ejemplo, lógica de predicado de primer orden, y preguntar sobre la integridad de un sistema axiomático. Suponga que trabaja en ZFC y cree que se compone de los axiomas naturales que representan el mundo. Ahora, cuando se le da un sistema axiomático diferente, puede preguntar si tienen la misma teoría y llamar a este sistema completo en caso de que la respuesta sea sí. Creo que la diferencia con el caso de la computabilidad es que, para la computabilidad, existe un consenso más fuerte sobre cuál debería ser el "modelo base". La razón de este consenso es que muchos modelos independientes de cómputo luego demostraron ser equivalentes,
fuente