¿Cómo saber si un idioma es reconocible, co-reconocible o decidible?

8

Si tiene un lenguaje L, sin hacer ninguna prueba, ¿hay alguna manera de saber si es reconocible, co-reconocible o decidible?

Básicamente, cualquier pista o truco que se pueda usar para contar. ¿O tal vez los patrones comunes a buscar para saber de qué tipo es?

omega
fuente
"sin hacer ninguna prueba", puedo demostrarte algo. (:
Ran G.
1
En matemáticas, un "truco" se suele llamar "teorema" y, en algunas ocasiones, un "lema".
Andrej Bauer el
Algunos patrones comunes son los abordados por el teorema de Rice (demostrando que un conjunto es indecidible) y el teorema de Rice-Shapiro (demostrando que un conjunto es irreconocible). Estos son particularmente útiles para el patrón "el conjunto de TM (codificadas)M tal que, corriendo Mobservamos este comportamiento "
chi

Respuestas:

6

L es reconocible

Un idioma L es reconocible si y solo si existe un verificador para L, donde un verificador es una máquina de Turing que se detiene en todas las entradas y para todos wΣ, wLcΣ.V accepts w,c. Comúnmente,c es considerado como un "certificado" o "prueba" de que w es en L y el verificador V comprueba si c es una prueba válida de w estar en L. (Tenga en cuenta que esta definición es equivalente a la definición del reconocedor porque podemos construir un reconocedor para un idioma a partir de un verificador para ese idioma). Ahora para determinar si un idioma está en RE o no, podemos hacer la siguiente pregunta:

Dada una cuerda wL, podrías probar esowL?

Por ejemplo, considere HALT={M,w | M is a TM that halts on w}. HALT es reconocible porque para demostrarte que M se detiene w, Solo puedo decirte la cantidad de pasos que debes seguir M para y si M se detiene después de tantos pasos, estaría convencido de que M,wHALT.

L es co-reconocible

Del mismo modo, un idioma L es co-reconocible si y solo si su complemento es reconocible, o en otras palabras, si existe un verificador para L¯. Por lo tanto, para ver si un idioma está en co-RE, podemos preguntar:

Dada una cuerda wL, podrías probar esowL?

Tomando nuevamente el ejemplo de HALT, podemos usar esta intuición para mostrar que HALTno es co-reconocible Esto es porque si te dijera que alguna máquinaM no se detiene en la entrada w, realmente no hay nada que pueda decirte para convencerte de ese hecho. podría correrM en w pero incluso si hemos estado mirando M correr y no lo he visto detenerse todavía, no sabemos que no se detendrá en algún momento en el futuro.

L es decidible

Finalmente un lenguaje L es decidible si ambos L y L¯son reconocibles Entonces, si la respuesta a las dos preguntas anteriores es sí, entonces el lenguaje es decidible.

Como ejemplo, considere L={anbn | nN}. Dada una cuerdawL, podría demostrarte que wL? Claro, podría contar la cantidad deasy el número de bsy muestran que son iguales, entonces Les reconocible ¿Qué pasa siwL? Podría probar que una cadena no está enL mostrando que tampoco es de la forma anbm o que hay una falta de coincidencia en el número de as y bs. Así,Les co-reconocible Dado que es reconocible y co-reconocible,L También es decidible.

Referencia: Soy un TA para una clase introductoria de teoría de la computabilidad / complejidad en mi universidad y mi profesor hizo esta guía animada realmente útil para razonar sobre lenguajes regulares, decidibles y reconocibles.

roctothorpe
fuente
Gracias por ese enlace! y gracias a tu profesor por hacer eso! fue genial
nulo el
2

Ideas principales

Ser reconocible significa que puede crear un proceso automático (volveremos a eso más adelante) que toma una palabra como parámetro de manera que

  • Si finaliza el proceso automático, devuelve SÍ o NO.
  • Este proceso automático no tiene que terminar en cada entrada, pero debe terminar si la palabra de entrada está en el idioma.

Ser co-reconocible significa el lenguaje wΣ,wL (o, en inglés, el conjunto de todas las palabras que no están en L, es decir, su complementario) es reconocible.

Ser decidible significa que puede crear un proceso automático que tome una palabra como entrada, de modo que

  • El proceso automático siempre termina
  • Responde SÍ o NO. Si responde SÍ, la palabra está en el idioma, si responde NO, la palabra no está en el idioma.

Un resultado importante es que L es decidible si y solo si L es reconocible y co-reconocible


La idea de probar este resultado es que puede construir un proceso automático a partir de los procesos que le brindan el reconocimiento y el reconocimiento conjunto, alternando los pasos de ambos procesos, hasta que uno de ellos le dé la respuesta SÍ. Uno de ellos tiene que hacerlo, ya que cada palabra está o no en el idioma)


Procesos automáticos

Sin ser demasiado formales, se han diseñado muchos tipos de máquinas, y básicamente todas se han vinculado a tipos de idiomas (esos tipos dependen de las herramientas necesarias para definir dichos idiomas. Para más información, la Jerarquía de Chomsky puede ayudar).

El significado habitual del proceso automático, con respecto a la capacidad de decisión, es una máquina de Turing. Puede definir una máquina de Turing de modo que pueda:

  • Recibir valores de la entrada
  • Almacenar valores
  • Lee los valores almacenados
  • Calcular operaciones matemáticas básicas sobre valores
  • Pruebe las propiedades matemáticas básicas en esos valores y actúe en consecuencia, eventualmente en bucle.

Básicamente, una máquina de Turing puede hacer todo lo que puede definir en un programa, excepto que es un objeto matemático, con memoria infinita y tiempo para gastar en un cálculo. No siempre termina.

Otra propiedad importante de las máquinas de Turing es que puede describir una máquina de Turing como una sola palabra (esto es codificación), y existe una máquina de Turing que, dada como entrada, codifica una máquina My una palabra w, puede simular el cálculo de M en la entrada w. Esto será importante en un momento.


Señalemos que los lenguajes regulares, que son (casi) el tipo de lenguaje más simple en el que se puede pensar desde el punto de vista matemático, tienen la propiedad peculiar de que están cerrados bajo el complemento. Esto básicamente significa que en esos idiomas, las nociones de reconocibilidad y capacidad de decisión son equivalentes. Esto no se cumple a medida que avanzas en la Jerarquía de Chomsky.


Ejemplo de lenguaje indecidible

Estudiaremos el problema de detención . La pregunta es, ¿podemos construir una máquina de Turing que, dada la codificación de otra máquina de TuringM y una palabra w, decide siM termina en la entrada w ?

Obviamente, esto es reconocible , ya que solo tenemos que simularM en whasta que termine, y cuando lo haga, diga SÍ. Sin embargo, siMnunca termina, no diremos NO, por lo que reconocemos este lenguaje, pero no lo decidimos. Se ha demostrado que este lenguaje no puede ser decidido por una máquina de Turing. Esto implica un esquema matemático habitual: un argumento diagonal, que no llamaría intuitivo. Puede consultar este boceto de prueba para acostumbrarse.

Para resumir

No podrá, dado un idioma, simplemente indicar si es decidible o no. No hay ningún algoritmo que pueda hacer eso, y demostrar que un idioma no es decidible requiere pensar, y puede requerir algún conocimiento sobre máquinas de Turing, argumentos diagonales, etc.

Sin embargo, aquí está mi forma personal de manejar esta pregunta. Por lo general, cuando estudio un idioma, supongo que es decidible, a menos que muestre alguna forma de referencia sobre la forma en que funciona Turing Machine. En ese caso, empiezo a desconfiar e intento definir un algoritmo para decidir el idioma. Si esto no parece fácil, a veces ayuda dividir el trabajo en algoritmos tanto de reconocimiento como de reconocimiento conjunto. Si todavía no puedo hacerlo, trataría de establecer una conexión entre este idioma y otro indecidible, como "Si puedo decidir ese idioma, puedo decidir el problema de detención". Esta es una reducción de Turing a un problema indecidible, por lo que el primer problema no puede ser decidible. Si todo eso falla, puedo intentar usar argumentos diagonales, pero esto puede ser un poco complicado.

wazdra
fuente
1

Un truco es que si el idioma es finito, entonces usted sabe con certeza que es decidible, ya que puede "codificar" una máquina para aceptar cualquier cosa en ese idioma. Sin embargo, creo que la forma más fácil es simplemente reducir de otro idioma

Steven
fuente
Los mismos trabajos para lenguajes co-finitos.
Raphael
Además, un lenguaje con un espacio de solución finita dada su entrada será decidible ya que puede realizar una búsqueda de fuerza bruta.
jmite
1

Como mencioné en mi comentario anterior, me resulta útil pensar en el espacio de solución del problema.

Piensa en algo como SAT. Sabemos que es decidible, ya que para probarlo hay un número finito de soluciones que tenemos que probar. Si hay un conjunto finito de condiciones para verificar, donde una de estas exitosas garantiza un sí, y ninguna de ellas exitosa garantiza un no, entonces el problema es decidible, ya que solo verificamos las condiciones en sucesión. Tenga en cuenta que este conjunto de condiciones podría ser muy grande (como en el caso de problemas con NP completo).

Considere ahora cuándo el espacio de la solución es infinitamente contable, y podemos generar cada solución posible en secuencia, y probar cada solución es decidible. En este caso sabemos que el problema es reconocible. Por ejemplo, un problema al preguntar "¿hay un número natural tal que ..." es reconocible, porque podemos comenzar en 0 y seguir intentando cada número en secuencia. Si hay una solución, estamos garantizados para encontrarla, pero no necesariamente hay un límite en el tiempo que llevará encontrarla. Además, este algoritmo nunca se detendría si no existiera tal número entero, por lo que no prueba que un problema sea decidible.

Puede aplicar la misma técnica al conjunto de todas las cadenas, todos los enteros, todos los gráficos o cualquier estructura finita que podamos enumerar. Esto no funcionaría para encontrar un número real o un conjunto (posiblemente infinito) de cadenas.

Sin embargo, tenga en cuenta que algunos problemas pueden tener innumerables espacios de solución infinitos y aún ser decidibles.

jmite
fuente
"Si el espacio de la solución es infinitamente contable, entonces sabemos que el problema es reconocible". -- No necesariamente. Primero, el espacio de la solución puede no ser enumerable de manera efectiva (Ejemplo: "¿Existe una TM que calcule una función total y de modo que [predicado no trivial]?"). En segundo lugar, la decisión de si el objeto considerado es una solución puede ser indecidible por sí misma (Ejemplo: "Encuentre una TM que no se detenga en 77").
Raphael
Ah, eso genera una idea. Lo sabemosNP{L| L Decidable}, por lo que eso implicaría que si podemos mostrar que un problema está en NP (o P para el caso), simplemente se deduce de eso. Eso podría ayudar a reducirlo.
Steven
Además: "Cualquier cosa con un" conjunto finito de posibilidades "para probar será decidible" - no. El problema de detención tiene dos respuestas posibles pero es indecidible.
Raphael
@ Steven Sí, pero esa es una prueba aún más difícil. (El conjunto al que se refiere generalmente se denota con R, el conjunto de idiomas recursivos (decididamente)).
Rafael
Supongo que debería aclararlo. La idea es que no se puede aplicar fuerza bruta al problema de detención de la manera en que se puede, por ejemplo, 3-SAT. O cómo, cuando ejecuta algo en un PDA, puede probar todas las rutas posibles aunque no sea determinista. Pero para un TM, no puede porque podría durar infinitamente, por lo que el conjunto de "cosas para probar", es decir, las posibles rutas a través del programa, no es finito.
jmite el
0

El truco para ver si un idioma es indecidible es hacerse la pregunta "¿puedo codificar un cálculo de la máquina de Turing usando este idioma"? O, más en general, "¿se vuelve tan complicado como lo que sucede en un cálculo?". Por supuesto, a veces esta codificación es difícil y ayuda a conocer una lista de problemas indecidibles para reducir (como el problema de correspondencia posterior). Si no encuentra tal reducción, intente pensar en algoritmos para decidir su idioma. Por ejemplo, el lenguaje de las listas de enteros en orden creciente no es finito, pero es fácil diseñar un algoritmo que pruebe si una lista está ordenada en orden creciente, por lo que este lenguaje es decidible. Y para muchos idiomas, no sabemos acerca de su capacidad de decisión, por lo que esta es una pregunta difícil.

Denis
fuente
Esta respuesta está promoviendo una intuición incorrecta, ver aquí .
Raphael
No estoy de acuerdo con que sea una intuición incorrecta. Por supuesto, no mencioné todos los problemas, por ejemplo, el lenguaje se puede presentar de una manera excesivamente complicada como en su ejemplo, por lo que primero hay que simplificarlo para llegar a su "esencia". Tampoco mencioné el hecho de que existen lenguajes indecidibles "arriba" deteniéndose, y "debajo" deteniéndose, porque no creo que ayude a la intuición a este nivel.
Denis