¿Qué es undecidability

Question

¿Qué significa que un problema es indecidible?

Por ejemplo, la detención problema.

Qué significa que los seres humanos nunca pueden inventar una nueva técnica que siempre decide si una máquina de turing se va a detener?

Si no, ¿qué técnicas se permitió que detener problema es indecidible?

Por ejemplo, la inducción es una buena técnica, ¿por qué no puedo uno descubra alguna nueva técnica?

Tengo problemas para entender cómo algunos de los nuevos invención no puede resolver la suspensión problema.

Dado que algunos de ordenador y un programa, es realmente insuficiente información almacenada en el mismo para determinar si va a detener?

Parece un problema puramente mecánico

Answer 1

Permítanme comenzar por señalar que, si hay un simple algoritmo para resolver el cese problema, gran parte de la matemática moderna sería completamente diferente. Por ejemplo, considere el siguiente programa:

1. n = 2

2. Prueba si 2n es una suma de dos números primos. Si no, la salida. De lo contrario, n = n+1 e ir al paso 1.

Si este programa se detiene es equivalente a la de Goldbach la conjetura! Para detener el problema es bastante barrido cosa. Así que la razón por la que este problema es irresoluble, no es que hay muy poca información codificada en ella, pero mucho, mucho.

El unsolvability de la detención problema significa específicamente que no hay ninguna máquina de Turing que, cuando se presentó con la entrada de otra máquina de Turing (en cualquier descripción razonable) y algunos datos de entrada, va a determinar si la entrada de la máquina de Turing se detendrá en la cadena de entrada (y de salida siempre una respuesta de si o no en una cantidad finita de tiempo). Esto no significa, por supuesto, se oponen a la gente a buscar maneras específicas para demostrar que específica máquinas de Turing de frenar o no frenar, pero significa que no hay ningún general de la forma (al menos, en la medida en que la "forma" significa "método que una máquina de Turing puede emular") que funcionará para cualquier programa.

Answer 2

En principio, podría ser una noción de computabilidad que va más allá de la noción de Turing la computabilidad. Que no hay es generalmente llamada la Tesis de Church-Turing. Hay una enorme cantidad de evidencia de la Tesis de Church-Turing. Pero a menos que declare que, por definición, computables a los medios de Turing computable, la Tesis no puede ser probado, ya que se dice que una cierta noción informal (la computabilidad) coincide con un formal de la noción.

Answer 3

En primer lugar, sí, a tu pregunta "¿esto significa que los seres humanos nunca pueden inventar una nueva técnica que siempre decide si una máquina de Turing se va a detener?", sobre todo porque las reglas del juego han sido: el formalismo de la Emt. (en este punto será útil para ir realmente en algunos de los detalles y ver la construcción que muestra que la asunción de la existencia de una TM de que los controles para impedir que se traduce en una contradicción).

Pero aún así, supongamos que a usted le dieron un mágico "nueva técnica" ...esto ha sido investigado bajo el nombre de 'oracle'...incluso con un oráculo que decide si una mt puede detener en la entrada dada, resulta que todavía hay problemas que no pueden solucionarse con una TM (por bastante similar paradójico de la construcción, que mostró que el viejo y simple detener problema es indecidible).

Aparte de todo eso, hay dos dificultades con la detención problema que podría dar lugar a malentendidos (si ignorando los detalles técnicos): saber lo que se está cuantificado más, y tratar con el infinito.

• lo que pide es un algoritmo (para ser implementado en un TM) que toma como entrada las especificaciones para otro TM y un parámetro y se supone para devolver la respuesta a las preguntas " ¿el dado TM detener para el parámetro de entrada?'. El punto es que, a pesar de que podría ser capaz de mostrar una particular TM que se detiene (o no) en la entrada, pero estás supone que debe ser capaz de demostrar que para-cualquier - TM. Ese es un tipo de orden de alto.

• el otro problema es, por una entrada que no se detendrá en el dado TM...bueno, usted no sabe que antes de tiempo, así que, ¿cómo saber si el TM se va para siempre, o simplemente tomar un tiempo muy largo? No se puede ejecutar cosas como el tiempo que quieras (que es una especie de la definición de infinito). Así que no es una estrategia posible, para comprobar -nonhalting - mediante la simulación.

Dado el resultado principal (no hay ningún algoritmo general que se muestran para-cualquier-TM si se detiene en una entrada determinada), resulta que, posiblemente en la dirección que usted está buscando, que para muchas subclases de todos los posibles TMs, no -son - los algoritmos que puede decidir si uno va a parar o no. Que es, quizás si que restringir su formalismo un poco, podría ser un compilador (la detención problema TM para esta subclase) que le dirá si usted tiene algunos molestos bucles infinitos en no (no se puede detener para algunos datos de entrada).