Esto no es realmente una respuesta, pero es demasiado largo para un comentario. Sólo quiero ofrecer algunos comentarios sobre los enlaces de respuesta. Re: real de sus preguntas, usted puede encontrar este artículo muy interesante.
Creo que Neel$^*$ comentario es un poco engañoso.
Vamos a empezar desde el lado básico de las cosas: cómo hacer grandes cardenales implica hechos acerca de la aritmética? (A través de Godelization, datos sobre el comportamiento del programa son "realmente" los hechos acerca de la aritmética.) La respuesta más sencilla es a través de la coherencia de las reclamaciones. La declaración de "ZFC es consistente" es una $\Pi^0_1$ frase (la aritmética de la jerarquía si usted no está familiarizado con él). También está implícito (más de ZFC) por la existencia de un débil inaccesible cardenal; esto es debido a que ZFC prueba la declaración de la "Si $\alpha$ es débilmente inaccesible, a continuación, $L_\alpha\models$ ZFC." Así que este es un ejemplo de un hecho acerca de la aritmética que es implicado por una gran cardenal de la declaración.
Esto puede ser directamente se convirtió en una declaración sobre la terminación del programa, de la siguiente manera. Para un determinado computably axiomatizable teoría de la $T$ (tales como ZFC), podemos escribir un programa $\pi_T$, lo que detiene el fib $T$ es inconsistente, básicamente, $\pi_T$ sólo busca una prueba de una contradicción de $T$, y se detiene el fib se encuentra uno.
Como un aparte: la tarea de encontrar razonablemente pequeños programas que "representan" a ciertas propiedades de una determinada teoría, o al menos que tengan propiedades que no puede ser comprobado en una teoría dada, es interesante. Ver, por ejemplo, este trabajo por Aaronson y Yedidia en un pequeño programa que se ejecuta siempre, pero que ZFC no pueden probar que duraría para siempre.
Esencialmente, los siguientes es un hecho básico acerca de la computabilidad y provability:
La consistencia de un determinado computably axiomatizable teoría de la $T$ es equivalente a la no terminación de un programa asociado a $T$, y la consistencia de las declaraciones siguen a menudo de grandes cardenales.
Para que un sentido en el que los grandes cardenales pueden conducir a las declaraciones sobre el comportamiento de los programas. Es incluso mejor que eso: el programa de $\pi_T$ asociado a $T$ es óptimo, en el sentido de que una teoría razonable (mucho mucho menos de ZFC - incluso menos de PA!) demuestra que $\pi_T$ termina iff $T$ es inconsistente. En particular, para cada gran cardenal axioma a podemos asociar un programa de $\sigma_A$ tal que $\sigma_A$ termina iff ZFC+a es inconsistente. Así:
La consistencia con ZFC de una gran cardenal axioma es equivalente a la no terminación de un determinado programa.
Por lo que este se conecta a la consistencia de los grandes cardenales con la no terminación de los programas.
Pero eso no es lo que Neel dijo! Dijo que los grandes cardenales fueron equivalentes a las declaraciones acerca de la terminación del programa.
Ahora en la cara de ella, esto es rotundamente falso: las declaraciones acerca de la terminación del programa son aritméticos de las declaraciones, y estos no pueden depender de la verdad real de gran cardenal axiomas. Precisamente, si a es (lo que generalmente se reconoce como) un gran cardenal axioma, entonces ZFC qué no probar "$\varphi$ es equivalente a Una" o incluso "$\varphi$ implica Un" para cualquier aritmética sentencia de $\varphi$ menos que ZFC en realidad refuta A.
Esto puede parecer misterioso, pero en realidad hay mucho menos de lo que el ojo. Revisión de un gran cardenal axioma A = "no es un cardenal $\kappa$ tal que [las cosas]." Las [cosas] siempre implica que ese $\kappa$ da un modelo de ZFC, es decir, que $L_\kappa\models$ ZFC (este es un problema sociológico reclamación acerca de lo que constituye un "gran cardenal" - el término "gran cardenal" no es precisa).
OK, así que supongo que ZFC no refutar A., a Continuación, por Gödel teorema de completitud, ZFC + a tiene UN modelo de $M$. Ahora vamos a $\kappa$ ser el menos ordinal en $M$ tal que cualquiera de las $M\models$[cosas]$(\kappa)$ o para algunos $\alpha\in Ord^M$, $\kappa\in L_\alpha^M$ y $L_\alpha^M\models$[cosas]$(\kappa)$. (Esto no es necesariamente el real menos el testimonio de Una - que podría ser más pequeño.) En la nota anterior, se ha $L_\kappa^M\models$ ZFC, pero por definición de $\kappa$ lo que también ha $L_\kappa^M\not\models$ A. sin Embargo, el conjunto de los números naturales no cambió entre el $M$ $L_\kappa^M$ (ya que todo lo que hicimos fue "cortado ( $L$ ) $M$ off" en algún nivel infinito), por lo $L_\kappa^M$ satisface todos la misma aritmética de los hechos como $M$ - en particular, el valor de verdad de $\varphi$ no cambio. Hemos demostrado:
Si a es Una gran cardenal axioma y $\varphi$ es una media aritmética frase coherente (más de ZFC) con Un, a continuación, $\varphi$ no prueba A.
Y el caso al $\varphi$ no es consistente (más de ZFC) con Un supuesto trivial, ya que, a continuación, $\varphi$ no puede ser equivalente (más de ZFC) con Un menos que sea inconsistente.
Así que ¿en qué sentido fue Neel la afirmación correcta?
Creo que él estaba haciendo un punto acerca de la semántica de los lenguajes de programación. Este no es un tema que yo sé mucho acerca, así que puedo estar equivocado, pero mi entendimiento queda de la siguiente manera:
La idea aquí es crear una estructura matemática asociada a un determinado lenguaje de programación. Mi entendimiento es que a menudo, si no generalmente, esta estructura es una categoría con diversas buenas propiedades y, posiblemente, una estructura adicional. Por cierto, los detalles precisos de la estructura puede ser sutil - ver, por ejemplo, esta discusión de si el "categórica" la semántica de Haskell en realidad es una categoría. (Estoy totalmente calificado para comentar sobre este tema específico, por el camino. Si usted está interesado, se puede hacer una pregunta aquí sobre ella.)
El punto ahora es que el siguiente puede, y al parecer no, se producen:
Hay una semántica $\mathcal{S}$ para un lenguaje de programación FOO, de tal manera que la no terminación de ciertos programas en FOO son equivalentes a la existencia de ciertas correspondientes gran cardenal axiomas, debidamente re-interpretado en el marco pertinente, en la estructura de la $\mathcal{S}$.
Es decir, la construcción de $\mathcal{S}$ desde FOO es de alguna manera canónica, y no estamos hablando de la no terminación de la reclamación en el sentido de la auténtica existencia de un gran cardenal, sino más bien en el sentido de un hecho acerca de la estructura interna del objeto $\mathcal{S}$.
Note la frase "debidamente re-interpretado." Un gran cardenal axioma en el lenguaje de la teoría de conjuntos no tienen sentido en el contexto de, por ejemplo, la categoría de teoría. En lugar de eso, tenemos que buscar un equivalente apropiado. Un puro ejemplo de esto es la equivalencia, debido a Blass, de la existencia de un cardinal medible y la existencia de un functor exacto $F$ a partir de Conjuntos de Conjuntos que no es, naturalmente, equivalente a la identidad. Ahora, si se nos ha dado algunos "apropiado" de la categoría de $\mathcal{C}$, tal vez tiene sentido decir "$\mathcal{C}$ piensa que existe un cardinal medible" iff la declaración "no es un functor exacto $\mathcal{C}\rightarrow\mathcal{C}$ no es equivalente a la identidad" es cierto.
Así que sospecho que esto es lo que Neel significa cuando dice que las afirmaciones acerca de la terminación son equivalentes a un conjunto teórico de reclamaciones: que cuando nos fijamos en la canónica de la semántica de un lenguaje de programación determinado, terminación hechos se reflejan en los internos conjunto teórico de las propiedades de la estructura.
$^*$No estoy seguro de lo que la etiqueta es con respecto a los nombres de; he usado el primer nombre, pero estoy feliz de utilizar el nombre completo o título profesional o etc. si ese es el mejor estándar.
