Pida a algunos de los comentarios en esta pregunta, me pregunto si nada se sabe sobre el lugar de la Conjetura de Collatz en la aritmética de la jerarquía. Más específicamente, es Collatz conocido por ser equivalente a un $\Sigma_1$ o $\Pi_1$ declaración? Es obvio que no puede ser expresado en el segundo nivel de la jerarquía, como $\forall n\exists k . C^{(k)}(n) = 1$ (y creo composición funcional es $\Delta_0$, por lo que el hecho de que estamos utilizando un ligeramente mayor que la lengua aquí debería ser discutible; podemos codificar el cómputo de ruta que intervienen en el cómputo de las $C^{(k)}(n)$ como una secuencia finita de números enteros y por lo tanto como un número entero por una adecuada codificación), pero no parece ser una manera obvia de expresar como un primer nivel de instrucción...
Respuestas
¿Demasiados anuncios?
Nunca he tratado mucho con la cuestión de la divergencia de trayectorias (condición (A) en mjqxxx's comentario), pero la cuestión de la existencia de órbitas (condición (B)) se puede traducir en una pregunta, si finita de conjuntos de $\small E_N $ de N entero parámetros $\small \left<A,B,C,\ldots,H \right> $ donde $\small A,B,\ldots,H>0 $ admite una solución racional de un sistema relacionado de ecuaciones lineales.
(Nota: los parámetros que se utilizan como exponentes de la "Syracuse"-formulación de la Collatz-problema: $\small x_{k+1}=(3x_k +1)/2^A $ donde $\small x_k $ es impar y es tal, que también se $\small x_{k+1} $ es impar).
Si se denota el número de los parámetros antes mencionados, como N y su suma como S entonces N y S deben estar en una (no es exacto, pero ajustada) en relación, por ejemplo, $\small 1.5 N < S< 2N $ por lo que los valores de los parámetros para cualquier conjunto $\small E_N $ superior acotado.
Por otra parte, el número de parámetros, que igual a 1 frente a aquello que exceda de 1 se relaciona con el hecho de que el 1 -parámetros de representar el aumento de y >1-parámetros de representar la caída de los pasos en el "Syracuse"-notación
A continuación, la cuestión de la existencia de trivial ciclos de cualquier longitud especificada N puede ser resuelto mediante la enumeración y la verificación de las soluciones: "tiene la solución valor entero?" asociado de la ecuación lineal que tiene la forma $\small x={Q(A,B,C,...,H) \over 2^S-3^N}$ donde $\small Q(\ldots) $ es una combinación lineal de potencias de 3 y 2 con exponentes hecho a partir de los parámetros a,B,...,H. La cantidad de cálculo para cada N es limitado por el número de combinatorical opciones para satisfacer las limitaciones mencionadas para el conjunto de los N parámetros . Este es un tipo de problema que puede ser resuelto por un supertask-máquina porque es subfactorial para cada N .
(He hecho una discusión relacionada con la existencia de ciclos en que "Syracuse"-ver el problema y la relación de la ecuación lineal de mí, pero una más profesional de la discusión de este punto de vista y la descripción de la ecuación (y para algunos tipos específicos de ciclos de un completo sistema de ecuaciones lineales) se realiza, por ejemplo, por John Simons 2007, un ejemplo en línea aquí , o mejor aún, aquí en una versión actualizada artículo conjunto con Benne de Weger de 2010, que acabo de encontrar aquí)
Como se sugiere en mi comentario anterior, voy a interpretar tu pregunta como preguntar si la conjetura de Collatz es demostrablemente equivalente a un $\Pi_1$ o $\Sigma_1$ frase más cierta de la base de la teoría de la $T$. Hay una gran variedad de cuestiones en juego en función del resultado de la conjetura (en el modelo estándar).
Caso 0: La conjetura de Collatz es falsa, porque algunos secuencia de Collatz es periódica con un periodo distinto de $4,2,1$. En ese caso, la conjetura de Collatz es demostrablemente equivalente a $0=1$ sobre cualquier teoría con el poder suficiente para codificar y decodificar el testimonio de la secuencia hasta su primera repetición (por ejemplo, PA o I$\Sigma_1$).
Caso 1: La conjetura de Collatz es falsa, porque algunos secuencia de Collatz nunca se repite. En ese caso, la conjetura es tal vez el equivalente a un $\Pi_1$ frase. Decir que la secuencia de Collatz de partida con algún tipo de norma número $n_0$ es no repetir nunca es una $\Pi_1$ declaración. En el extraño caso en el que la Collatz secuencias que no se repiten son precisamente las que van a través de $n_0$, entonces la conjetura de Collatz es equivalente a $\Pi_1$ declaración. Más generalmente, si hay un (estándar) lista finita $n_0,n_1,\dots,n_k$ de manera tal que el Collatz secuencias que no se repiten son, precisamente, los que van a través de uno de estos, entonces también tenemos un $\Pi_1$ frase equivalente a la conjetura de Collatz. Todavía más en general, si hay una secuencia computable $n_0,n_1,\dots$ con esa propiedad, también tenemos una $\Pi_1$ frase equivalente a la conjetura de Collatz. Sin embargo, en caso de no computable secuencia existe, entonces es poco probable que podamos hacer mejor que $\Sigma_2$ menos que el uso de un no-axiomatizable base de la teoría como de la $\Pi_1$ teoría del modelo estándar.
Caso 2: La conjetura de Collatz es cierto. En ese caso, la conjetura de Collatz es equivalente a la afirmación de que $g(n) = (\mu k)(C^k(n)=1)$ total computable de la función. Podemos, a continuación, compare $g$ a los diversos niveles del rápido crecimiento de la jerarquía para un análisis más preciso. Por ejemplo, si $g(n)$ está acotada arriba por algunos $f_k$ donde $k$ es finito, entonces $g$ realidad, es primitiva recursiva y la conjetura de Collatz es demostrablemente cierto en I$\Sigma_1$ (como PA excepto que la inducción se limita a $\Sigma_1$ fórmulas). Si $g(n)$ es abundaban por encima de algunos $f_\alpha$$\alpha \lt \varepsilon_0$, entonces la conjetura de Collatz es demostrablemente cierto en PA. Si $g$ crece más rápido de lo que entonces aún más fuerte la teoría es necesaria para demostrar la conjetura de Collatz.
Ver http://matwbn.icm.edu.pl/ksiazki/aa/aa91/aa9146.pdf "Un binomio representación de la 3x + 1 problema" por Maurice Margenstern y Yuri Matiyasevich.
