.6.1 Problemas insolubles para la teoría de lenguajes

Problemas de decisión.

Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”.

Problemas de decisión.

Un problema de decisión es

Soluble si existe un algoritmo total para determinar si la propiedad es verdadera (Existe una MT que siempre para al resolver el problema).

Parcialmente soluble si existe un algoritmo parcial para determinar si la propiedad es verdadera (existe una MT que resuelve el problema, pero puede no parar).

Insoluble si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una MT),

Ejemplos de problemas de decisión:

¿Existe un algoritmo para decidir si un número natural cualquiera es par?

Si es soluble.

¿Existe un algoritmo para decidir si dos autómatas finitos cualesquiera son equivalentes?

Si es un problema soluble.

¿Existe un algoritmo para determinar si una gramática es ambigua o no?

No es insoluble.

Muchos problemas insolubles son paradójicos en su naturaleza. Ej: la paradoja de Russell.

Un peluquero afecta a todas las personas que no se afectan a si mismas. El peluquero: ¿se afeita así mismo? (insoluble).