Conjeturas matemáticas equivalentes a la detención de una máquina de Turing

11

Esta pregunta es sobre si cada teorema matemático puede reducirse a la pregunta de si una sola máquina de Turing se detiene. En particular, estoy interesado en conjeturas que actualmente no están probadas.

Por ejemplo: Wikipedia dice que actualmente se desconoce si hay números perfectos impares. Como es decidible si un número dado es perfecto, uno podría escribir una máquina de Turing que verifique cada número impar por turno y se detenga si encuentra uno que sea perfecto. (Esta máquina de Turing no toma ninguna entrada.) Si supiéramos si esa máquina de Turing se detiene, entonces sabríamos si la conjetura es cierta, y viceversa.

Sin embargo, como otro ejemplo, ¿qué pasa con la conjetura de primos gemelos ? Es decidible si un número dado es el primer primo en un par gemelo, pero en este caso no podemos detenernos cuando encontramos el primero, porque la pregunta es si hay un número infinito. No me queda claro si es posible hacer una máquina de Turing que se detenga si y solo si la conjetura de los primos gemelos es cierta.

Seguramente podemos hacer una máquina de Turing que se detenga si y solo si la conjetura de primos gemelos es demostrable dentro de la aritmética de Peano o algún otro sistema formal, pero esa es una pregunta diferente, ya que podría ser cierto pero no demostrable en el sistema particular que elegimos.

Entonces mis preguntas son

¿Es posible hacer una máquina de Turing que se detenga si y solo si la conjetura de primos gemelos es verdadera? (Y si es así, ¿cómo?)
¿Es posible, en general, hacer una máquina de Turing que se detenga si y solo si alguna afirmación matemática dada es verdadera? ¿Puede esta máquina de Turing construirse algorítmicamente a partir de la declaración formal?
Si no es posible en general, ¿hay alguna forma de clasificar las declaraciones matemáticas en si son equivalentes a la detención de una sola máquina de Turing, o una máquina de Turing con un oráculo , etc.? Si es así, ¿es esta clasificación decidible para una declaración dada?

formal-languages computability mathematical-foundations Nathaniel
fuente

¿Qué significa "verdadero"? ¿Con qué tipo de modelos estamos evaluando esta verdad en relación? Tendrás que definir eso primero, creo.

Jake

Creo que todas esas máquinas de Turing solo pueden probar la demostrabilidad. Incluso si no está iterando explícitamente sobre declaraciones verdaderas en PE, todavía está buscando una prueba en otra forma. La diferencia es que la existencia de un número perfecto impar obviamente no puede ser tanto verdadera como no demostrable, mientras que los primos gemelos sí.

Karolis Juodelė

Cualquier conjetura sobre conjuntos incontables no puede expresarse utilizando máquinas de Turing.

Raphael

12

Su pregunta es respondida por la jerarquía aritmética . La existencia de un número perfecto impar es una declaración , por lo que puede probarlo usando una máquina , que se detiene si la declaración es verdadera. La conjetura de doble primo es una declaración , por lo que puede construir una TM con acceso al oráculo de detención que se detiene si la declaración es falsa. $\Sigma_1$ $\Sigma_1$ $\Pi_2$

En un sentido lógico estricto, siempre puede hacer una máquina de Turing que detenga la declaración iff : $\phi$

Si mantiene, entonces tome una máquina que se detenga. $\phi$
Si no se mantiene, entonces tome una máquina que no se detenga. $\phi$

Para ver que esta construcción es válida, considere la forma lógica de su declaración:

\forall ϕ \exists T . ϕ \Leftrightarrow T halts .

$\forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}.$ Puede aclarar esta confusión haciendo preguntas ligeramente diferentes:

¿Qué es un conjunto de declaraciones tal manera que exista una máquina de Turing que se detenga en iff es válida? $\Phi$ $\phi \in \Phi$ $\phi$

Arriba he indicado que las declaraciones de forman tal conjunto. $\Sigma_1$

Yuval Filmus
fuente

Gracias, creo que la jerarquía aritmética es exactamente lo que estaba pidiendo. Creo que lo que realmente pretendía preguntar era "¿hay una función computable total desde (algún subconjunto de) enunciados matemáticos hasta máquinas de Turing que no tienen entrada, de modo que la máquina correspondiente a un enunciado dado se detiene si el enunciado es verdadero?" Pero, por supuesto, eso es equivalente a la versión que propusiste.

Nathaniel

0

¡Sea , , y seapara cada número entero . Para un entero positivo , deje que denote la declaración: si un sistema $f(1)=2$ $f(2)=4$ $f(n+1)=f(n)!$ $n \geq 2$ $n$ $\Theta_n$

S \subseteq {x_{i}! = x_{k} : i, k \in {1, \dots, n}} \cup {x_{i} \cdot x_{j} = x_{k} : i, j, k \in {1, \dots, n}}

$S \subseteq \{x_i! = x_k: i,k \in \{1,\ldots,n\}\} \cup \{x_i \cdot x_j=x_k: i,j,k \in \{1,\ldots,n\}\}$

solo tiene muchas soluciones finitas en enteros mayor que , entonces cada solución satisface . Conjeturamos que las declaraciones son verdaderas. $x_1,\ldots,x_n$ $1$ $(x_1,\ldots,x_n)$ $\min(x_1,\ldots,x_n) \leq f(n)$ $\Theta_1,\ldots,\Theta_{16}$

La afirmación demuestra la implicación: si existe un primo gemelo mayor que , entonces hay infinitos primos gemelos, consulte este documento de A. Tyszka ( En los conjuntos tal que el infinito de es equivalente a la existencia en de un elemento que es mayor que un número umbral calculado utilizando la definición de ) $\Theta_{16}$ $f(16)+3$ $W \subseteq \mathbb{N}$ $W$ $W$ $W$

Es decir, suponiendo la declaración , una sola consulta a decide el problema principal doble. $\Theta_{16}$ $0'$

Apoloniusz Tyszka
fuente

Conjeturas matemáticas equivalentes a la detención de una máquina de Turing

Respuestas: