Demuestre que la Conjetura de Collatz sería demostrable si pudiéramos resolver el problema de detención

Question

Este es el problema 5.31 de Introducción a la teoría de la computación, 3ª edición, de Michael Sipser.

Dejemos que $$ f(x) = \begin{cases} 3x+1, & \text{for odd $x$} \\ x/2, & \text{for even $x$} \end{cases} $$ para cualquier número natural $x$ . Si se comienza con un número entero $x$ e iterar $f$ se obtiene una secuencia, $x$ , $f(x)$ , $f(f(x))$ , $\dots$ . Detente si llegas a 1. Por ejemplo, si $x = 17$ se obtiene la secuencia 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Extensas pruebas informáticas han demostrado que todo punto de partida entre 1 y un número entero positivo grande da una secuencia que termina en 1. Pero la cuestión de si todos los puntos de partida positivos terminan en 1 no está resuelta; se llama la $3x + 1$ problema.

Supongamos que $A_{TM}$ = $\{\langle M,w\rangle$ $M$ es una máquina de Turing y $M$ acepta $w\}$ (Máquina de Turing de aceptación) fueran decidibles por una Máquina de Turing $H$ . Utilice $H$ para describir una máquina de Turing que garantice la respuesta a la $3x + 1$ problema.

Answer 1

Supongo que la pregunta es: si podemos resolver el problema de detención, ¿podemos averiguar la respuesta a la $3x+1$ ¿Problema (Collatz)?

Bueno, si tenemos un programa $H$ que resuelve el problema de detención (es decir, puede decidir si una máquina de Turing $M$ con entrada $I$ se detiene o no), entonces haga lo siguiente:

Crear una máquina de Turing $F$ que toma un número $x$ e itera a través del $f(x)$ y se detiene al llegar a $1$ . Es fácil demostrar que tal máquina de Turing $F$ existe .. aquí está su pseudocódigo:

F (entrada $i$ )

$Begin$

$\quad$ Mientras que $i \not = 1$

$\quad \quad $ Caso $i$ está en paz: $i = i/2$

$\quad \quad $ Caso $i$ es impar: $i = 3*i+1$

$End$

(Así que esta rutina F se detendrá siempre que la secuencia termine con un 1 ... de lo contrario, continuará para siempre)

Ahora crea una nueva máquina de Turing $C$ que comienza con un determinado $i$ y que llama a la detención del programa $H$ en $F$ y $i$ . Si $H$ dice que $F$ no se detiene en $i$ y luego se detiene. Si $H$ dice que $F$ se detiene $i$ , a continuación, aumentar $i$ por $1$ y repetir el proceso. Una vez más, es fácil demostrar que tal máquina de Turing $C$ existe, suponiendo que $H$ existe .. aquí está su pseudocódigo:

C (entrada $i$ )

$Begin$

$\quad$ Mientras que $H(F,i)$

$\quad \quad$ $i=i+1$

$End$

(por lo que esta rutina $C$ sólo se detendrá si por alguna $i$ , $H$ encuentra que $F$ no se detiene en $i$ . Efectivamente, $C$ busca un contraejemplo a la conjetura de Collatz. Si hay uno, entonces $C$ acabará encontrándose con él. Si no lo hay, entonces $C$ se ejecutará para siempre)

Por último, llame a $H$ en $C$ y $1$ . Si $H$ dice que $C$ con $1$ no se detendrá, entonces aparentemente la solución a la $3x+1$ es que la secuencia siempre terminará con $1$ para cualquier $x$ (es decir, no hay ningún contraejemplo a la conjetura de Collatz... por lo que la conjetura de Collatz es cierta). Si $H$ dice que $C$ con $1$ se detiene, entonces aparentemente la solución es que para algunos $x$ la secuencia no termina con $1$ (es decir, hay un contraejemplo a la conjetura de Collatz). Así que, de cualquier manera, se ha resuelto la $3x+1$ El problema de Collatz.