¿Puede una máquina de Turing (TM) decidir si el problema de detención se aplica a todas las TM?

9

En este sitio hay muchas variantes sobre la cuestión de si las TM pueden decidir el problema de detención, ya sea para todas las otras TM o ciertos subconjuntos. Esta pregunta es algo diferente.

Pregunta si el problema de detención se aplica a todas las TM puede ser decidido por una TM. Creo que la respuesta es no, y deseo verificar mi razonamiento.

Defina el lenguaje de meta-detención como el idioma compuesto por TM que deciden si una TM se detiene. $L_{MH}$

L_{M H} = {M : \forall_{M^{'}, w} M (M^{'}, w) accepts if M^{'} (w) halts, rejects otherwise}

$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$

$L_{MH}= \emptyset$ debido al problema de detención.

Por lo tanto, la pregunta del título establece con mayor precisión: ¿es decidible si ? $L_{MH} = \emptyset$

Según el teorema de Rice, es indecidible si un idioma está vacío.
En ambos casos, si es o no es re, no se puede determinar si . $L_{MH}$ $L_{MH} = \emptyset$
Por lo tanto, no se puede determinar si . $L_{MH} = \emptyset$

Esto demuestra que una TM no puede decidir si el problema de detención se aplica a todas las TM.

¿Es correcto mi entendimiento?

ACTUALIZACIÓN: Estoy tratando de demostrar que una TM no puede "probar el problema de detención" para alguna definición de "probar" que parece intuitivamente correcta. A continuación se muestra una ilustración de por qué creo que esto es correcto.

Podemos crear un TM que genere de la siguiente manera. El TM toma una tupla . Simula para iteraciones de . Si acepta todos los que se detienen y rechaza todos los demás, entonces acepta . De lo contrario, rechaza si decide incorrectamente o no se detiene. $M_{MH}$ $L_{MH}$ $(M_i,M_j,w_k,steps)$ $M_i(M_j, w_k)$ $steps$ $M_i$ $(M_j, w_k)$ $M_{MH}$ $M_i$ $M_i$ $M_i$

$M_{MH}$ no se detiene, ya que debe evaluar un número infinito de pares para cada . Además, todos los s no se detendrán. no podrá aceptar o rechazar ningún ya que no sabrá por simulación que todos los s no se detendrán. Por lo tanto, el lenguaje que define no es re y no es decidible. $M_i$ $M_i$ $M_{MH}$ $M_i$ $M_i$

$M_{MH}$ captura mi intuición de lo que creo que significa para una TM probar el problema de detención. Otras sugerencias, como rechazar todo o una prueba conocida, dan a conocimiento previo de que el problema de detención se aplica a todos los . Esto no puede contar como probando algo ya que la premisa de es la conclusión que está demostrando, y por lo tanto es circular. $M_{MH}$ $M_i$ $M_{MH}$ $M_i$ $M_{MH}$ $M_{MH}$

computability turing-machines undecidability halting-problem Yters
fuente

3

Tu solución no ayuda. Un problema sin parámetros siempre es decidible, ya sea por una máquina de Turing que siempre genera SÍ o por uno que siempre genera NO. Su argumento no funciona, desafortunadamente. El verdadero análogo del teorema de Gödel es el teorema de Rice.

Yuval Filmus

55

"Pregunta si el problema de detención se aplica a todas las TM puede ser decidido por una TM". - esa consulta no tiene sentido ya que el problema de detención no se "aplica" a un conjunto de TM. Al menos, no sé qué se supone que significa eso.

Raphael

44

Has entendido mal el teorema de Rice. El teorema de Rice establece (en un caso especial) que el lenguaje es indecidible. No indica que es indecidible; de hecho, es decidible.

{M : L (M) = \emptyset}

$\{ M : L(M) = \emptyset \}$

\emptyset

$\emptyset$

\emptyset

$\emptyset$

Yuval Filmus

77

Creo que el malentendido está en lo que significa la expresión "decidir X". Formalmente, X debería ser un predicado en las cadenas, y luego una máquina que decida que X es aquella que en la entrada s emite el valor de verdad de X ( s ). ¿Cuál es el predicado en tu caso? ¿Cuál es su entrada y cuándo es verdad?

Yuval Filmus

55

La pregunta es un error de categoría. La capacidad de decisión es una propiedad de los lenguajes (conjuntos de cadenas), no de proposiciones matemáticas. Cualquier pregunta de la forma "¿Es decidible?" donde no es un conjunto de cadenas simplemente no tiene sentido.

X

$X$

X

$X$

David Richerby

5

Otro punto de vista: dejemos que sea una formalización de la declaración " " en ZFC ; (trivialmente) tenemos: $\varphi$ $L_{MH} = \emptyset$

el conjunto es decidible; $P = \{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\}$
También puede crear un TM que enumere las pruebas en ZFC y se detenga si encuentra una prueba de o una prueba de ; claramente detiene; $M$ $\varphi$ $\neg \varphi$ $M$
el conjunto es indecidible $\{ M \mid M \mbox{ decides } P \}$

Vor
fuente

19

El lenguaje de las máquinas de Turing para decidir el problema de detención es decidible. Una máquina de Turing que decide que simplemente siempre genera NO.

En otras palabras, es decidible. $\emptyset$

Puede confundirse con el hecho de que el lenguaje de las máquinas de Turing cuyo lenguaje está vacío es indecidible. Es decir, no hay una máquina de Turing que, en la entrada , decida si . $T$ $L(T) = \emptyset$

Yuval Filmus
fuente

77

El lenguaje vacío es decidible. Tratar con él.

Yuval Filmus

15

El lenguaje de las máquinas de Turing para decidir el problema de detención está vacío. El lenguaje vacío es decidible. Por lo tanto, el lenguaje de las máquinas de Turing para decidir el problema de detención es decidible.

Yuval Filmus

1

La pregunta es si un TM puede decidir el idioma de las máquinas de Turing que deciden que el problema de detención está vacío. Un TM no puede hacer esto como he mostrado anteriormente.

dice

1

@yters ¿Estás preguntando si un TM puede probar que ese idioma está vacío? Puede hacerlo fácilmente, simplemente emitiendo una prueba conocida existente.

user253751

3

¿Qué significa incluso que una TM demuestre algo?

Yuval Filmus

2

No entiendes el teorema de Rice.

El teorema de Rice, en este contexto, dice que no se puede decidir el problema "¿T decide el lenguaje vacío?".

Su problema no es decidir si una máquina Turing arbitraria decide el idioma vacío. Su problema es si existe o no una M que decida el idioma vacío.

Y tal M existe. Puede hacerlo incluso mejor que eso: en realidad puede construir tal M y proporcionar una prueba de que decide el lenguaje vacío.

El problema general de no ser decidible no significa que no pueda resolver instancias específicas. De hecho, por el dispositivo habitual de enumerar todas las pruebas, existe una máquina de turing que:

Acepta todas las máquinas de Turing para las cuales existe una prueba de que decide el idioma vacío.
Rechaza todas las máquinas de Turing para las cuales existe una prueba de que no decide el idioma vacío
No se detiene si no se puede probar de ninguna manera.

fuente

1

La definición sobre la capacidad de decisión de Wikipedia :

Un lenguaje recursivo es un lenguaje formal para el cual existe una máquina de Turing que, cuando se le presenta una cadena de entrada finita , se detiene y acepta si la cadena está en el idioma, y se detiene y rechaza lo contrario. La máquina de Turing siempre se detiene: se conoce como un decisor y se dice que decide el lenguaje recursivo.

En otras palabras, es decidible si hay una máquina de Turing que decide todas las cadenas de entrada. Es indecidible si para cada máquina de Turing, no decide todas las cadenas de entrada, lo que significa que podría decidir ninguna o algunas cadenas, pero hay al menos una (pero prácticamente al menos infinita de ellas) que no puede decidir.

$L$ $L = \emptyset$ $L_{MH} = \emptyset$

usuario23013
fuente

¿Puede una máquina de Turing (TM) decidir si el problema de detención se aplica a todas las TM?

Respuestas: