¿Es decidible la decidabilidad?

Me pregunto si decidir la capacidad de decisión del problema es un problema decidible. Supongo que no, pero después de las búsquedas iniciales no puedo encontrar ninguna literatura sobre este problema.

computability undecidability decision-problem sincronizar
fuente

Yo, amigo, he oído como decidibilidad así que ...

David Richerby

Su pregunta no responde en su forma actual, como lo muestran las dos respuestas que básicamente dicen "Trivialmente, no" y "Trivialmente, sí" (con un comentario adicional que dice "no" al "no"). Ha preguntado si un problema es decidible, pero no ha definido cuál es ese problema. En particular, ¿cuál es la entrada? Si desea diseñar una máquina de Turing

que le dirá si un problema es decidible, usted tiene que dar ese problema como una entrada a

. ¿Pero cómo haces eso?

M

$M$

M

$M$

David Richerby

Dadas las respuestas actuales, está la pregunta "¿Decidir Decidir Decidible Decidible Decidible?", Pero no voy a preguntar :-)

Mark Hurd

Respuestas:

Edición importante de mi original:

Parece una lectura ingenua de tu pregunta, deja que sea el problema $P$

Dado un lenguaje, , ¿es decidible? $P=$ $L$

Entonces preguntas

¿ es decidible? $P$

Como DW y David han notado, la respuesta es "sí, lo es", aunque no sabemos cuál de los dos decisivos triviales es el correcto. Para enmarcar su problema de modo que no sea tan trivial, sugeriría esto. En primer lugar, vamos a restringir cosas poco considerando sólo los lenguajes que son los idiomas aceptados por algunos TM . La razón para hacerlo es que si un TM no es aceptado por un TM, entonces no es re (reconocible) y, por lo tanto, no puede ser recursivo (decidible). Entonces podemos refundir como $L(M)$ $M$ $P$

Dada una descripción, de un TM, es decidable? $P'=$ $\langle M\rangle$ $M$ $L(M)$

Ahora es un lenguaje de descripciones TM, en lugar de un lenguaje de lenguajes como parecía ser (bajo una interpretación generosa), y ahora es perfectamente razonable preguntar si el lenguaje es decidible. Bajo esta lectura, el lenguaje que consiste en descripciones TM no es decidible. Esta es una consecuencia fácil del Teorema de Rice . Entonces ahora tenemos dos respuestas: mi "no" y el "sí" de DW, dependiendo de la interpretación. $P'$ $P$ $P'$

{⟨ M ⟩ ∣ M is a TM and L (M) is decidable}

$\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}$

Rick Decker
fuente

¡Gracias! Entender, al menos superficialmente, ambas respuestas me dio la información que estaba buscando, que es aproximadamente: "¿Podemos crear una máquina que pueda decidir lo que puede y no puede decidir en general?" (No es una buena redacción, lo sé, pero no puedo pensar en una mejor redacción). Muy útil, especialmente porque usted reconoce ambas interpretaciones.

sincronización

Pensé que demostrar que para cada problema decidible hay un certificado (algoritmo con una prueba) y para cada problema indecidible también hay un certificado (reducción del problema indecidible) es suficiente.

rus9384

Como hemos visto en las diferentes respuestas, parte de la respuesta está en formular el problema correcto.

En 1985, Joost Engelfriet escribió "La no computabilidad de la computabilidad" (Boletín del EATCS número 26, junio de 1985, páginas 36-39) como respuesta a una pregunta planteada por un estudiante inteligente. Desafortunadamente, el BEATCS era en ese momento solo papel y el artículo no dejaba rastros electrónicos.

$\Psi$ $F(m,n)$ $f:\Bbb N \to \Bbb N$ $m,n\in \Bbb N$ $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ $\underline m$ $m$

Yo cito:

$\Phi$ $\Bbb N \to \Bbb N$ $f$ $f$

La parte divertida está en la siguiente observación realizada en el artículo:

$\Phi$

Hendrik Jan
fuente

Si. Siempre es decidible.

Para cualquier problema P, que Q sea el problema de determinar si P es decidible o no. Afirmo que Q es decidible. Este es el por qué. Tautológicamente, o P es decidible o no lo es. Entonces, uno de los dos programas es correcto: (1) print "yup P is decidable"o (2) print "nope P is not decidable". Puede ser que sea no trivial de averiguar cuál de estos dos programas es correcta, una de ellas es correcta, por lo que un partido decisivo para Q sin duda existe . Por lo tanto, el problema Q es decidible.

Esto recuerda la siguiente pregunta clásica: ¿es decidible decir si la conjetura de Collatz es cierta? La respuesta es sí. Esto puede parecer extraño, ya que nadie sabe si la Conjetura de Collatz es cierta (ese es un famoso problema abierto). Sin embargo, lo que sí sabemos es que la Conjetura de Collatz es cierta o no lo es. En el primer caso, el programa print "yup it's true"es decisivo. En el último caso, el programa print "nope it's not true"es decisivo. No sabemos cuál es un decisor válido, pero esto es suficiente para demostrar que existe un decisor válido. Por lo tanto, el problema es decidible.

DW
fuente

Creo que la interpretación de Ricky Decker de la pregunta es superior. Dada alguna codificación de un problema, decida si el problema es decidible.

Yuval Filmus

@YuvalFilmus, OK, eso es razonable. ¿Tiene una codificación finita para problemas (es decir, idiomas) que cree que es razonable y no hace que el problema sea trivial? La codificación finita natural para un idioma es como una máquina de Turing que reconoce ese idioma, pero eso hace que el problema sea trivial, como lo ilustra su comentario sobre la respuesta de Ricky Decker. Por lo tanto, necesitaríamos alguna otra codificación razonable, que no sufra este tipo de problema. ¿Tienes alguna sugerencia para eso?

Puede usar la lógica de primer orden en algún lenguaje apropiado. O la entrada podría ser una máquina en 0 '(por ejemplo), es decir, una máquina Turing con acceso a un oráculo de detención.

Yuval Filmus

Según el teorema de Rice, sabemos que incluso decidir R en el universo RE es indecidible. ¿No es eso suficiente? (No todas las TM son decisivas)

Raphael

¡Gracias! Si bien, no la interpretación que pretendía, esto me ayudó a ver por qué la pregunta que hice podría no estar suficientemente bien expresada para reflejar mis intenciones.

sincronización