6 votos

¿Aprovechable = probadamente accesible?

Pregunta: Llamemos a un número real $x$ accesible si existe una máquina de Turing $M$ tal que $M(1), M(2),\dots$ es una secuencia que converge a $x$ . Si podemos demostrar ( editar : En ZFC) que la secuencia converge, decimos que $x$ es probadamente accesible . ¿Cualquier número abordable es también abordable de forma demostrable?

Despeje: Otra forma de plantear la misma pregunta es: ¿Es cierto que: "Si existe una máquina de Turing M tal que x es el límite de los valores de salida, entonces existe una máquina de Turing M' que converge al mismo número, y podemos demostrar que converge".

Observaciones: No sé si estos conceptos tienen nombre, sólo he inventado la terminología: Si tienen nombres, por favor haz un comentario, para que pueda cambiarlo ( editar : Aproximable se denomina "computable en el límite", pero no sé si existe un nombre para demostrablemente appoachable. "Aproximable" se ha utilizado mucho en las respuestas, así que he decidido no cambiarlo en la pregunta). Todos los números computables son demostrablemente aproximables pero no todos los números demostrablemente aproximables son computables (la constante de Chatins es un contraejemplo). No sé cuál es la relación entre abordable y definible (ni siquiera sé si existe una definición aceptada de número definible).

5voto

JoshL Puntos 290

Este post está marcado como wiki comunitario porque es sólo una elaboración de cómo entiendo la pregunta.

Para precisar esta cuestión, yo haría esta definición:

A número real comprobable en una teoría $T$ es una máquina de Turing $A$ tal que $T$ demuestra que $A$ enumera una secuencia convergente de números racionales.

Por otro lado, un número real $z$ es accesible si existe una máquina de Turing $M$ tal que $M$ enumera una secuencia de racionales que convergen a $z$ . La afirmación ``todo número real abordable es demostrablemente abordable'' significa entonces que, para todo número real abordable $z$ hay una máquina $M$ tal que $M$ enumera una secuencia de racionales que convergen a $z$ y $T$ demuestra que $M$ enumera una secuencia convergente de racionales.

Los reales abordables suelen llamarse "computables por el límite" en la literatura, debido al siguiente resultado.

Teorema. Un número real es abordable si y sólo si su expansión binaria es computable a partir del problema de detención, lo que ocurre si y sólo si la expansión binaria es un $\Delta^0_2$ cuando se ve como un subconjunto de $\mathbb{N}\times\{0,1\}$ .

Esta es la pregunta tal y como la leo.

Pregunta 1. ¿Cualquier número real abordable es demostrablemente abordable en ZFC? (ZFC puede ser sustituida por cualquier otra teoría efectiva).

La cuestión no es: dada una máquina de Turing que sabemos que es total, ¿podemos demostrar en ZFC que la máquina es total? En cambio, la cuestión es, esencialmente: si tenemos una máquina de Turing $A$ que resulta ser total en el modelo estándar, ¿hay alguna otra máquina de Turing $M$ que computa la misma función en entradas estándar, pero que también es probadamente total? (Nótese que en general la función computada en un modelo arbitrario es una extensión de la función computada en el modelo estándar porque ahora también hay entradas no estándar). Todavía no sé la respuesta, pero creo que es una pregunta muy interesante.

Cuando escribí por primera vez este comentario, tenía en la cabeza la idea de número real "demostrablemente computable" en lugar de "demostrablemente abordable". Se puede hacer la misma pregunta para eso:

Pregunta 2. ¿Es todo número real computable demostrablemente computable en ZFC, donde computable significa que la expansión binaria es c.e. y demostrablemente computable significa que hay alguna máquina que enumera la expansión binaria y que ZFC demuestra que es total?

Esto es esencialmente equivalente a la primera pregunta, porque la primera pregunta es sólo la relativización de la segunda a $0\prime$ .

5voto

Tim Howland Puntos 3650

Tras una discusión con Russell Miller, tengo una respuesta a la pregunta. De hecho, hay un real abordable que no es abordable de forma demostrable.

Adoptaremos PA como teoría base, aunque la construcción puede adaptarse fácilmente a otras teorías. Describiré una máquina de Turing $M$ que produce una secuencia convergente de números racionales, pero cualquier máquina de Turing $M'$ que PA demuestra que produce una secuencia convergente de números racionales converge a un número diferente de $M$ lo hace.

La idea es diagonalizar contra cualquier prueba de este tipo que se pueda descubrir. Fijar una enumeración de las máquinas de Turing $M_n$ . Consideremos la siguiente máquina de Turing $M$ . Nuestra máquina en la etapa $k$ producir un número racional $r_k$ dando un número finito de dígitos trinarios, pero utilizando sólo los dígitos 0 y 1 y no el 2, para evitar problemas de legibilidad no únicos. A medida que avanza la construcción, enumeramos sistemáticamente todas las pruebas posibles de la teoría. Es posible que en algún momento encontremos $k$ que existe una prueba de que la máquina de Turing $M_n$ produce una secuencia convergente de números racionales. En este caso, ejecutamos $M_n$ para $k$ pasos, obteniendo el racional actual $q_{n,k}$ aproximación al real al que $M_n$ está convergiendo. En este caso, si $r_k$ es diferente de $q_{n,k}$ por dígito $n$ , entonces utilizamos $r_{k+1}=r_k$ ; de lo contrario, producimos $r_{k+1}$ al dar la vuelta a la $n$ -dígito de $r_k$ de $0$ a $1$ o viceversa para garantizar que $r_{k+1}$ es diferente de $q_{n,k}$ . (Nota, estamos invirtiendo el $n$ -dígito, no el $k$ -dígito, por lo que cada máquina $M_n$ está vinculado al $n$ -enésimo dígito de nuestro límite real). Y simplemente proceder con este plan, teniendo en cuenta las nuevas pruebas como aparecen.

Tenga en cuenta que cada máquina $M_n$ que produzca de forma demostrable una secuencia convergente se considerará infinitas veces, para tamaños cada vez más grandes $k$ ya que hay muchas pruebas de que lo hace. Así que lo relevante $k$ para $M_n$ será arbitrariamente grande. Dado que $M_n$ se ha demostrado que produce una secuencia convergente, se deduce que los valores de $q_{n,k}$ realmente convergen y, por tanto, acaban estabilizándose en su primera $n$ bits (si esos bits son todos $0$ s y $1$ s). Por lo tanto, vamos a dar la vuelta a la $n$ -en nuestra parte racional $r_k$ como máximo un número finito de veces. Se deduce que nuestra secuencia $r_k$ es una secuencia convergente de números racionales.

Pero además, se deduce que siempre que haya una prueba de que alguna máquina $M_n$ produce una secuencia convergente de números racionales, entonces el límite de nuestro real diferirá del límite de esa máquina en un dígito $n$ .

Por lo tanto, tenemos un real abordable que no es demostrablemente abordable, como se desea.

Permítanme comentar el confuso punto sutil aquí sobre en qué teoría hemos probado que nuestra máquina produce una secuencia convergente de racionales. La respuesta es que lo hemos hecho en cualquier teoría que sepa que cualquier afirmación que sea demostrable en la teoría base es de hecho verdadera, ya que necesitábamos saber que cuando encontráramos una prueba de que $M_n$ produce una secuencia convergente de racionales, que esos racionales realmente convergen. Por ejemplo, ZFC tiene esta relación con PA, ya que ZFC demuestra que si $\varphi$ es demostrable en PA, entonces $\varphi$ es cierto. Pero más generalmente, para cualquier $\omega$ -Teoría coherente $T$ podemos extender a una teoría más fuerte $T^+$ que conoce esta implicación.

2voto

Tim Howland Puntos 3650

Su pregunta es vaga, lo que impide una respuesta. Esto es demasiado largo para un comentario, así que lo escribo aquí.

En primer lugar, no has dicho cuáles son los axiomas de tu sistema de pruebas. Si tenemos un sistema formal muy débil, por supuesto, obtendrás una respuesta negativa, ya que no podremos demostrar gran cosa. Pero a medida que el sistema se hace más fuerte, seremos capaces de demostrar más. (En un sistema inconsistente, por supuesto, podemos demostrar cualquier cosa.) Así que quizás lo que realmente estás preguntando es si, digamos, ZFC o PA son ya lo suficientemente fuertes como para demostrar los casos que te interesan.

Sin embargo, en segundo lugar, ¿qué afirmación es la que debe ser demostrable, exactamente? Parece que quieres suponer que un verdadero $x$ es abordable, y preguntar de este real en particular si es demostrable que es abordable. Pero, por supuesto, ZFC no sabe qué real en particular $x$ de la que hablas, a menos que proporciones una descripción de la misma. Entonces, ¿qué quiere decir? Ya que hemos supuesto que $x$ es abordable por alguna máquina de Turing $M$ entonces la única descripción sensata de $x$ que tenemos es simplemente "el límite de los valores emitidos por $M$ ". Pero en este caso, la cuestión se convierte en la trivialidad de probar la afirmación: "El verdadero $x$ que es el límite de los valores de salida de la máquina de Turing $M$ es el límite de los valores de salida de alguna máquina de Turing".

Así que parece que la pregunta quiere ser aclarada.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X