Problemas decidibles e indecidibles en Teoría de la Computación

Prerrequisito – Máquina de Turing

Se dice que un problema es decidible si siempre podemos construir un algoritmo correspondiente que pueda responder el problema correctamente. Podemos entender intuitivamente los problemas decidibles considerando un ejemplo simple. Supongamos que se nos pide que calculemos todos los números primos en el rango de 1000 a 2000. Para encontrar la solución de este problema, podemos diseñar fácilmente un algoritmo que pueda enumerar todos los números primos en este rango.

Ahora hablando de Decidibilidad en términos de una máquina de Turing, se dice que un problema es Decidible si existe una máquina de Turing correspondiente que se detiene en cada entrada con una respuesta , sí o no . También es importante saber que estos problemas se denominan Turing Decidible ya que una máquina de Turing siempre se detiene en cada entrada, aceptándola o rechazándola.

Problemas semidecidibles:
los problemas semidecidibles son aquellos en los que una máquina de Turing se detiene en la entrada que acepta, pero puede detenerse o hacer un bucle indefinido en la entrada que rechaza la máquina de Turing. Estos problemas se denominan problemas reconocibles de Turing .

Ejemplos: ahora consideraremos algunos problemas decidibles importantes :

• ¿Son equivalentes dos idiomas regulares L y M ? Podemos verificar esto fácilmente usando la operación Establecer diferencia. LM =Nulo y ML =Nulo. Por lo tanto (LM) U (ML) = Nulo, entonces L,M son equivalentes.

• ¿Membresía de una CFL?
  Siempre podemos averiguar si existe una string en una CFL determinada mediante el uso de un algoritmo basado en la programación dinámica.
• Vacío de una CFL
  Al verificar las reglas de producción de la CFL, podemos establecer fácilmente si el lenguaje genera strings o no.

Problemas indecidibles:
los problemas para los que no podemos construir un algoritmo que pueda responder el problema correctamente en un tiempo finito se denominan problemas indecidibles. Estos problemas pueden ser parcialmente decidibles pero nunca serán decidibles. Es decir, siempre habrá una condición que llevará a la Máquina de Turing a un bucle infinito sin proporcionar ninguna respuesta.

Podemos entender los problemas indecidibles intuitivamente al considerar el teorema de Fermat , un problema indecidible popular que establece que tres enteros positivos a, b y c para cualquier n>2 nunca pueden satisfacer la ecuación: a^n + b^n = c^n.

Si alimentamos este problema a una máquina de Turing para encontrar una solución que dé una contradicción, entonces una máquina de Turing podría funcionar para siempre, para encontrar los valores adecuados de n, a, b y c. Pero siempre no estamos seguros de si existe o no una contradicción y, por lo tanto, llamamos a este problema un problema indecidible .

Ejemplos: estos son algunos problemas indecidibles importantes :

• ¿Si un CFG genera todas las strings o no?
  Como un CFG genera strings infinitas, nunca podemos alcanzar la última string y, por lo tanto, es Indecidible.
• ¿Si dos CFG L y M son iguales?
  Como no podemos determinar todas las strings de cualquier CFG, podemos predecir que dos CFG son iguales o no.
• ¿Ambigüedad de CFG?
  No existe ningún algoritmo que pueda verificar la ambigüedad de una CFL. Solo podemos verificar si alguna string particular de la CFL genera dos árboles de análisis diferentes, entonces la CFL es ambigua.
• ¿Es posible convertir un CFG ambiguo dado en un CFL no ambiguo correspondiente?
  También es un problema indecidible ya que no existe ningún algoritmo para la conversión de una CFL ambigua a una CFL no ambigua.
• ¿Es regular un aprendizaje de idiomas que es un CFL?
  Este es un problema indecidible ya que no podemos encontrar en las reglas de producción de la CFL si es regular o no.

Algunos problemas indecidibles más relacionados con la máquina de Turing:

• ¿Problema de pertenencia de una máquina de Turing?
• ¿Finitud de una máquina de Turing?
• ¿ Vacío de una máquina de Turing?
• ¿Si el lenguaje aceptado por Turing Machine es regular o CFL?

Leer los siguientes artículos – Decidibilidad , Indecidibilidad y Reducibilidad