Problemas De Decicion En Computabilidad

Problema de decisión

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 dedecisión es un problema en donde las respuestas posibles son «sí» o «no». Un ejemplo típico de problema de decisión es la pregunta: ¿Es un número entero dado primo? Una instancia de este problema sería: ¿Es17 primo?
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 conjuntocontiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los números primos se puede ver también como el lenguaje de todas las frases en elalfabeto {0, 1,..., 9} tales que el entero correspondiente es primo.
Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que elproblema 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 correindefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible. En Teoría de la computabilidad, se estudia qué lenguajes son decidibles con diferentes tipos demáquinas. En teoría de la complejidad computacional se estudia cuántos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, número de procesadores, tipo de máquina, etc.).Ejemplos
Esos 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 frases sobre elalfabeto {a, b, c} que contienen igual número de letras a y b.
* Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y...