Teoria de la computacion

UNIDAD 5. Decibilidad.

5.1 Lenguajes Decidibles. 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 «sí» o «no». Un ejemplo típico de problema de decisión es la pregunta: ¿Dado un número entero es primo? Una instanciade este problema sería: ¿Es 17 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 conjunto contiene 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 detodas las frases en el alfabeto {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 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 qué lenguajes son decidibles con diferentes tipos de máquinas. Un lenguaje decidible es aquel lenguaje L para el cual existe una maquina de Turing que puede aceptar cualquier cadena w∈ L. Hay lenguajes formados por cadenas tales queuna maquina de Turing logra un estado final con las cadenas que reconoce y acepta, solamente. En este caso se dice que la máquina de Turing semidecide al lenguaje. Los lenguajes semidecididos por una MT se llaman recursivos numerables. Las gramáticas sin restricciones son las que generan los lenguajes recursivos numerables. De

aquí en adelante será suficiente referirse a los lenguajesrecursivos numerables, pues estos generalizan a los lenguajes recursivos, los cuales generalizan a los lenguajes libres de contexto, y estos a los lenguajes regulares. Lo anterior tiene relación directa con que los autómatas de Turing generalizan a los de la pila y estos a su vez a los autómatas finitos. Por otro lado, pese a que lenguajes formales más generales que los recursivos numerables no sonreconocidos por un automata de Turing, no existe hasta el momento ningún autómata más poderoso capaz de reconocerlos. En terminos de procedimientos, las cadenas de un lenguaje decidible corresponden a procedimientos que terminan, ya sea realizando lo que indica la palabra ó señalando que no tienen la capacidad de realizarlo. Para un lenguaje semidecidible, las cadenas decididas por la MT soninstrucciones realizadas por la MT. De manera complementaria, las cadenas no decidibles por la MT corresponden a procedimientos que no terminan utilizando una maquina de Turing. A partir de lo dicho aquí tenemos la definición de algoritmo: Un algoritmo es una implementación de una maquina de Turing tal que el conjunto de sus entradas es el lenguaje decidible. Es decir, si dado un conjunto de entradas bajolas cuales una MT logra un estado de parada para cada entrada, la maquina corresponde a la implementación de un algoritmo. Esta es la Tesis de Church – Turing. No es un teorema pues no se puede demostrar matemáticamente, de manera general y categórica. Es solo la afirmación de que el concepto informal del algoritmo corresponde a un objeto matemático. Al ser solo una afirmación no demostrable. Paraque esto ocurra, se necesitaría encontrar un autómata más potente que uno de Turing tal que fuese capaz de realizar la implementación de un algoritmo. Si bien hay algunas propuestas interesantes que pretende generalizar a la MT, hasta la fecha ninguna de ellas ha sido aceptada para sustituir nuestro actual concepto de procedimiento comprable. Por otro lado, mientras que los lenguajes computables...