¿Existe una máquina de Turing conocida que se detiene si y sólo si la conjetura de Collatz tiene un contraejemplo?

Question

Algunas de las más simples e interesantes conjeturas no probadas en matemáticas son la conjetura de Goldbach, la hipótesis de Riemann y la conjetura de Collatz.

La conjetura de Goldbach afirma que cada número par mayor o igual a 4 puede ser escrito como la suma de dos números primos. Es bastante sencillo cómo crear un programa de ordenador que se detenga si y sólo si existe un contraejemplo a la conjetura de Goldbach: simplemente se pasa en bucle sobre todos los números enteros, se comprueba si cada uno es un contraejemplo, y se detiene si se encuentra un contraejemplo.

Para la hipótesis de Riemann, también hay un programa de ordenador "conocido" que se detiene si y sólo si existe un contraejemplo.

(Dado el enunciado habitual de la hipótesis de Riemann, esto no está tan claro, pero el artículo de Jeffrey C. Lagarias " Un problema elemental equivalente a la hipótesis de Riemann "muestra que la hipótesis de Riemann es equivalente a la afirmación de que una cierta secuencia de números enteros $L$ es un límite inferior para una cierta secuencia de números reales $R$ . La secuencia $L$ es computable, y $R$ es computable con una precisión arbitraria, así que nuestro programa de computación sólo necesita computar todos los elementos de $R$ en paralelo, y detenerse si se descubre que algún elemento es más pequeño que su correspondiente elemento en $L$ .)

¿Pero qué hay de la conjetura de Collatz?

La conjetura de Collatz establece que para todos los números enteros positivos $n$ la "secuencia de granizo" $H_n$ finalmente llega $1$ .

Podríamos intentar hacer lo mismo que hicimos con la conjetura de Goldbach: hacer un bucle sobre todos los números enteros positivos $n$ y detenerse si alguna vez se encuentra un contra-ejemplo. Pero hay un problema aquí: con la conjetura de Collatz, dado un entero positivo $n$ no es obvio que se pueda decidir si es o no $n$ es un contraejemplo. No podemos simplemente "comprobar si $n$ es un contraejemplo" como podemos con la conjetura de Goldbach.

Así que es hay una conocida máquina de Turing que se detiene si y sólo si la conjetura de Collatz es falsa?

Por supuesto, una "máquina de Turing conocida" no tiene que ser una máquina de Turing que alguien ha construido explícitamente; si es sencillo cómo escribir un programa de ordenador que haga esto, entonces eso cuenta como una "máquina de Turing conocida".

Por otro lado, decir "es la máquina que trivialmente se detiene, o es la máquina que trivialmente no se detiene" no cuenta como una "conocida máquina de Turing"; estoy pidiendo una respuesta que mencione una sola La máquina de turing $M$ (sin entrada ni salida), de tal manera que sabemos que $M$ se detiene si y sólo si la conjetura de Collatz es falsa.

Answer 1

Notemos que no se trata de si Collatz es indecidible. La declaración $ \neg\mathrm {Con}(PA)$ es indecidible (por $PA$ asumiendo $PA$ es consistente) pero sin embargo $ \neg\mathrm {Con}(PA)$ equivale a la parada de una cierta máquina de Turing (la que busca la prueba de una contradicción en PA).

Más bien, la cuestión es si

hay un $ \Pi ^0_1$ declaración $ \varphi $ de tal manera que el problema de Collatz, que en su cara es $ \Pi ^0_2$ ya se sabe que es equivalente a $ \varphi $ .

Aquí ya conocido significa en particular que no se nos permite asumir que Collatz es o no es demostrable o refutable en ningún sistema en particular, a menos que ya lo sepamos.

La mejor prueba de que no existe tal $ \varphi $ parece estar en el periódico mencionado por @Burak:

Kurtz, Stuart A.; Simon, Janos , La indecidibilidad del problema generalizado de Collatz Cai, Jin-Yi (ed.) y otros, Teoría y aplicaciones de los modelos de computación. 4ª conferencia internacional, TAMC 2007, Shangai (China), 22-25 de mayo de 2007. Actas. Berlín: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 542-553 (2007). ZBL1198.03043 .

A saber, dan una familia parametrizada de problemas similares, de tal manera que la colección de parámetros para los cuales Collatz para esos parámetros es verdadera, es $ \Pi ^0_2$ -completo y por lo tanto no $ \Pi ^0_1$ .

Pueden hacer esto sin resolver el problema de Collatz, al igual que Matiyasevich y otros pudieron demostrar que la resolución de la ecuación de la diofantina era $ \Sigma ^0_1$ -completo, sin que por ello se resuelva ninguna ecuación en particular por sí mismo.

Si Collatz pudiera simplificarse de alguna manera a un $ \Pi ^0_1$ entonces muy plausiblemente la versión generalizada podría también por el mismo argumento (cualquiera que sea ese argumento hipotético) pero que El show de Kurtz y Simon no sucederá.

Answer 2

¿El Big Bang se define como antes o después de la inflación?

La palabra "definido" hace que esto sea una cuestión de opinión más que de hecho. Siempre intento atenerme a los hechos determinados a partir de pruebas empíricas. Pero hey ho, haré lo mejor que pueda.

Parece una pregunta bastante simple para responderla bien. Y si ayer mismo me hubiera encontrado con esto, habría dado una respuesta definitiva. Pero he estado leyendo mientras escribía mi tesis y estoy encontrando definiciones conflictivas del Big Bang.

Eso es porque hay confusión en la cosmología.

Todo el mundo está de acuerdo en que en la cosmología estándar del Big Bang, el Big Bang se define como la singularidad; el momento en el tiempo en el que el factor de escala llega a cero.

Muchos cosmólogos podrían estar de acuerdo en eso, pero IMHO va demasiado lejos para decir que todos están de acuerdo en una singularidad. Una singularidad a veces denota un problema, indicando que una teoría ha ido mal. Creo que es posible arrojar algo de luz sobre el universo primitivo pensando en la gravedad, la relatividad y los agujeros negros, y apreciando que no hay un punto central - la singularidad en un agujero negro.

Vale, pero cuando incluyes la teoría de la inflación, se pone un poco turbia.

La teoría de la inflación es definitivamente "un poco turbia". No el universo en expansión, la inflación. Me gusta pensar que se llega a una posición en la que la inflación es una solución a un problema que no existe.

Así que esto es lo que quiero decir con definiciones conflictivas. Como ejemplo, en The Primordial Density Perturbation de Lythe y Liddle, definen el Big Bang como el comienzo de la era de la gravedad atractiva después de la inflación.

Esa no es una definición que yo usaría. Por cierto, note que la gravedad siempre es atractiva, y que altera el movimiento de la luz y la materia a través del espacio, pero no hace que el espacio se caiga. La gran crisis no ocurrió cuando el universo era pequeño y denso, y no va a ocurrir nunca.

Sin embargo, la Cosmología Moderna de Dodelson define el Big Bang como algo que viene antes de la inflación; utiliza efectivamente la vieja definición de que el Big Bang es el momento en que el factor de escala se acerca a cero.

Creo que eso es mejor, pero no del todo correcto. Es una especie de no se ha dado cuenta del truco .

Esta contradicción es evidente en múltiples lugares. Al hacer una búsqueda en Google, uno puede encontrar muchas explicaciones persuasivas para ambas definiciones. Todas las definiciones coinciden en que ya no podemos definirla como la singularidad donde a=0. Pero cada una tiene sentido a su manera y así, me confundo cada vez más sobre cuál es la correcta cuanto más la leo.

Ninguno de ellos es exactamente correcto.

El argumento para el Big Bang que viene después es que la teoría inflacionaria difiere de la cosmología estándar del Big Bang alrededor del 10 −30 s.

Olvídalo. No hubo inflación.

antes de que esperemos encontrarnos con la singularidad

Olvida eso también. No había ninguna singularidad.

cuando la inflación terminó, y que no tenemos evidencia de nada que venga antes de eso, por lo tanto el big bang se define ahora como las condiciones iniciales para el universo caliente y en expansión que se establecen por y al final de la inflación.

No hay evidencia de inflación. Pero hay confusión en la cosmología.

El argumento para que el Big Bang llegue antes parece ser que la inflación sigue siendo un período en el que el factor de escala crece y, como tal, el Big Bang puede definirse como el valor más cercano a cero (que es antes de la inflación), o más bien, el momento más temprano en el que el factor de escala se acerca a cero. Esto parece basarse esencialmente en decir "bueno, lo definimos como el momento en que el factor de escala era más pequeño antes de que se añadiera la inflación". ¿Por qué no seguir teniendo eso como la definición después de que se añade la inflación?"

El gran flequillo se asocia con cosas que se hacen más grandes. No tiene sentido definir el big bang como algo que ocurre después de que el universo se hizo mucho más grande rápidamente.

El primer argumento tiene mérito porque define el comienzo de la época en la que el universo es descriptible (prácticamente) por la cosmología estándar del Big Bang. Pero el segundo argumento tiene mérito por su simplicidad y porque utiliza el espíritu de la definición original; el factor de escala más pequeño y el momento en que la expansión del universo parece comenzar.

Si no hubiera inflación, las cosas serían mucho más sencillas, ¿no?

Por lo tanto, mi pregunta principal: ¿Qué definición es correcta? ¿Digamos que el Big Bang vino antes o después de la inflación?

No computa . No hubo inflación. Sobre esa base, la segunda definición es más correcta, pero no del todo correcta. PD: Me di cuenta tu comentario sobre el documental. Si desea consultar me Por favor, no dudes en enviarme un correo electrónico a mi nombre a btconnect punto com. ¡LOL!