Decibilidad

5. DECIBILIDAD
5.1 LENGUAJES DECIDIBLES
Un problema de decisión es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo "si/no".
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 unalgoritmo 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).
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuencia deinstrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
La teoría de computabilidad tiene como objetivo el estudio de problemas de decisión, con el fin de determinar si los mismos son teóricamente decidibles.
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.
¿Es un número entero dado primo? Una instancia de este problema sería: ¿Es 17 primo?
* Si es un problema soluble.
¿Existe un algoritmo para determinar si una gramática es ambigua o no?
* Es insoluble.
Muchos problemas insolubles son paradójicos ensu naturaleza. Ejemplo: la paradoja de Russell o paradoja del barbero, demuestra que la teoría original de conjuntos formulada por Cantor y Frege es contradictoria.
Un peluquero afeita a todas las personas que no se afeitan a sí mismas. El peluquero: ¿se afeita así mismo? (insoluble).
En un lejano poblado de un antiguo emirato había un barbero llamado As-Samet diestro en afeitar cabezas ybarbas. Un día el emir se dio cuenta de la falta de barberos en el emirato, y ordenó que los barberos sólo afeitaran a aquellas personas que no pudieran hacerlo por sí mismas. Cierto día el emir llamó a As-Samet para que lo afeitara y él le contó sus angustias:
-- En mi pueblo soy el único barbero. No puedo afeitar al barbero de mi pueblo, ¡que soy yo!, ya que si lo hago, entonces puedo afeitarme pormí mismo, por lo tanto ¡no debería afeitarme! Pero, si por el contrario no me afeito, entonces algún barbero debería afeitarme, ¡pero yo soy el único barbero de allí!
En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son SI oNO.
Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, también llamado lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva.
Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entoncesse dice que el problema es decidible, de otra forma se dice que es un problema indecidible. Cuando existe un algoritmo que puede responder positivamente cuando la frase está en el lenguaje, pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible. En Teoría de la computabilidad, se estudia cuales lenguajes son decidibles condiferentes tipos de máquinas. En teoría de la complejidad computacional, se estudia cuantos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, número de procesadores, tipo de máquina, etc.).
Estos son algunos ejemplos de problemas de decisión expresados como lenguajes:
* Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
* Las...