Hay resultados conocidos que la versión generalizada de la conjetura de Collatz es indecidible. Me pregunto por qué un caso especial de ello todavía puede ser decidible. ¿No debe el caso general aplicar resultados a todos los casos especiales?
Respuestas
¿Demasiados anuncios?
saulspatz
Puntos
116
Sólo porque un problema no puede ser resuelto, no se sigue que los casos específicos no pueden ser resueltos. El general de quinto grado del polinomio no puede ser resuelto por radicales, pero sin duda no son particulares de quinto grado de las ecuaciones que puede ser.
Un profesor una vez me dio este ejemplo de un problema indecidible, cada una de cuyas instancias se decidable. Para cada entero positivo $n$, vamos a $P(n)$ ser la prueba en el primer orden de teoría de la aritmética con número de Gödel $n$. A continuación, la instrucción, $\exists n, P(n)$ es una prueba de que $0=1,$ es indecidible. Pero para cualquier $n$ sin duda podemos decidir. No es un procedimiento eficaz para la generación de $P(n)$ y, a continuación, examinamos la última línea para ver si dice $0=1.$
Hume2
Puntos
377
No podemos decidir si la generalización es verdadera o falsa. Eso significa que no podemos usar ningún algoritmo que nos diga qué casos especiales son verdaderos y cuáles son falsos. Sin embargo, resolver un caso especial no nos dice nada acerca de todos los otros casos en general. Por lo tanto, aún podremos decidir si un subconjunto de todos los casos especiales es verdadero.
Mees de Vries
Puntos
165
No es el caso general se deben aplicar los resultados para todos los casos especiales?
Parece que su confusión se deriva de esta. La frase "caso general" aquí se usa de forma diferente de cómo se interprete. En algunas situaciones, "caso general" significa que se aplica a todas las instancias de un problema. En esta situación, significa que todos los problemas se toman juntos crear un problema indecidible.
El teorema de enlace de los estados que no existe ningún terminación de máquina de Turing, la cual puede tomar los números de $P, a_0, b_0, \ldots, a_{P-1}, b_{P-1}$ y de salida $0$ si el correspondiente Collatz conjetura es falsa, y $1$ si el correspondiente conjetura de Collatz es cierto.
El caso especial significa aquí: hay una máquina de Turing que puede tomar la (específicos) número $2, 1/2, 0, 3, 1$ y de salida $0$ si el ordinario de la conjetura de Collatz es falso, o 1 si el ordinario de la conjetura de Collatz es cierto? La respuesta es trivialmente que una máquina de Turing que existe: la máquina de Turing que siempre salidas de 0 va a hacer, o el que siempre salidas 1. Simplemente no sabemos lo que uno es, sin embargo.
