¿CCR puede solucionar el problema de parada?

Question

Estaba leyendo algo de lo que dijo:

Menos convencional es la Rápida Aceleración de la Computadora (RAC) cuyo reloj se acelera exponencialmente rápido, con pulsos en (digamos) veces $1-2^{-n}$ n tiende a infinito. RAC puede meter un número infinito de cálculos en un solo segundo.Es indiferente a la complejidad algorítmica de la tarea: todo lo que se ejecuta, no en exponencial o polinomio de tiempo, pero en los acotados de tiempo.Por lo tanto, puede resolver la suspensión problema para máquinas de Turing (que Turing demostró a través de algoritmos indecidible) mediante la ejecución de un cálculo en la aceleración del tiempo y lanzando un botón en particular, si y sólo si la máquina de Turing se detiene. Como todos los cálculos llevados a cabo por el RAC, todo el procedimiento se completa en un segundo: es entonces suficiente para inspeccionar el interruptor para ver si ha sido lanzado.

Creo que entiendo lo que está diciendo. Pero también siento que la normal de diagonalización argumento podría mostrar que los Ccr no puede decidir la suspensión problema.

Alguien puede ayudarme a aclarar mi confusión?

---

EDIT: con Base en los comentarios, creo que podría ser malentendido de la suspensión problema a un nivel fundamental. Así que aquí es mi impresión; esperemos que alguien puede señalar el error:

Teorema (*): Vamos a $S$ ser el conjunto de todas las cadenas binarias de countably de longitud infinita. Entonces no hay un bijection entre los números naturales y $S$.

Esto es demostrado por diagonalización; dejando $HALT=0$ $NOT\ HALT=1$ etc. hemos de conseguir que la aplicación de este teorema para Máquinas de Turing.

Las posibilidades parecen ser:

1. (*) es falso
2. Ccr no proporcionan un bijection

Suponiendo la verdad de ( * ), ¿por qué no los Rac mostrar un bijection? Ccr puede iterar a través de todos los TMs, por lo tanto la construcción de un "bijection mesa".

Answer 1

Se siente como si usted está mezclando el uncountability de los reales con el undecidability de la detención problema - mientras la diagonalización argumentos están relacionados, eso no quiere decir que 'no bijection entre los programas y la detención de miembros como usted dice en su comentario sobre la cuestión.

La mejor manera de pensar de la 'detener problema" podría ser esta: en primer lugar, el conjunto de Máquinas de Turing es contable, y por lo que podemos poner en correspondencia uno a uno con los números enteros (se puede ver por qué?). Puesto que la entrada a un determinado TM también puede ser representado como un entero, y ya que hay una correspondencia uno a uno a partir de pares de enteros a enteros, podemos reformular la pregunta: "¿la Máquina de Turing con índice de $x$ alto en la entrada de $y$?", la pregunta " que es el entero $\left<x,y\right>$ en la detención de establecer $H$?'. (Se puede ver por qué esto es equivalente a la pregunta '¿la Máquina de Turing con índice de $z$ alto en el vacío de la entrada?')

La diagonalización argumento, a continuación, muestra que ningún TM puede calcular el conjunto de $H$ -, pero eso no implica que el conjunto de $H$ no existe. Es perfectamente válido objeto matemático, y podemos estudiar; lo que es más, podemos imaginar que sabemos que el conjunto de $H$ (en otras palabras, que tenemos una de oracle que toma un entero como entrada y nos dice si ese entero es en $H$ o no) y pregunte qué problemas se pueden resolver con conocimiento de $H$, y por otra parte si hay problemas que no tienen solución, aun sabiendo $H$. Pero ahora, ya que varias personas han sugerido, el mismo estilo de diagonalización argumento funciona a través de las máquinas de los que saben el conjunto $H$' para ofrecer un nuevo conjunto de $L$ de la máquina de los índices, que incluso las máquinas con conocimiento de $H$ no se puede calcular si un entero dado es en el conjunto de $L$ o no. Que pasa, podemos en realidad (como sdvcc sugiere en los comentarios) la construcción de una serie infinita de conjuntos de números enteros tales que incluso una máquina con un oráculo para el conjunto anterior de esta serie no se puede determinar la pertenencia en el siguiente juego. Estos son generalmente etiquetados como $0', 0'', \ldots, 0^{(n)}$ donde $0^{(n+1)}$ es (esencialmente) el 'detener set' de los índices de máquinas con conocimiento de $0^{(n)}$. Pero tenga en cuenta que cada conjunto $0^{(i)}$ es sólo otro conjunto de números enteros.

De hecho, incluso hay conjuntos de números enteros - vamos a llamar a una $I$ - de tal forma que un regular de la Máquina de Turing no puede calcular el conjunto de $I$ (es decir, no puede responder a las preguntas 'es el número de $x$$I$?), pero una Máquina de Turing con el conjunto $I$ todavía no pueden responder a preguntas acerca de la detención problema $H$; $I$ se dice que es un intermedio , y la existencia de estos grupos no fue demostrado por varias décadas después de que el concepto de la TM fue descubierto. Si estás interesado en más detalles sobre este tipo de preguntas de ¿qué Máquinas de Turing puede y no se puede calcular, la magia de las palabras para buscar son la Teoría de la Recursividad - hay un poco más el tema de lo que yo podría incluso comenzar a pista aquí.

Answer 2

Diagonalización sólo puede ser utilizado para mostrar una máquina de tipo $X$ no puede resolver la suspensión problema para las máquinas de tipo $X$.

Esta máquina no es una máquina de turing, (ni siquiera es un equipo de acuerdo al uso convencional), por lo que es coherente que resuelva la detención problema para máquinas de turing, pero no puede resolver la suspensión problema de RAC.

Para su edición:
Sólo hay un countably número infinito de máquinas de turing. Así como hay countably muchos números naturales. Pero hay innumerables muchos infinito de cadenas binarias, así como hay innumerables muchos números reales.