LENGUAJES DECIDIBLES
Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un posible alfabeto sería, digamos, {a, b} , y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba .
Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas quecontienen el mismo número de símbolos que , por ejemplo
La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.
Esos son algunos ejemplos deproblemas de decisión expresados como lenguajes:
* Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
* Las frases sobre el alfabeto {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 un camino en el grafo que es el camino máscorto entre esos dos vértices.
* Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se para en un tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuencia de instrucciones universalmente precisas yentendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivo el estudio de problemas de decisión, con el fin de determinar si los mismos sonteóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en establecer una medida de la cantidad de recursos computacionales (en términos de tiempo y/oespacio) necesarios para resolver un determinado problema o equivalentemente reconocer un lenguaje
LOS PROBLEMAS RESOLUBLES SE SUBDIVIDEN EN TRATABLES E INTRATABLES
Los problemas tratables son: Aquellos para los cuales existe un algoritmo eficiente que los resuelve.
Los intratables son: Aquellos para los cuales no se conoce (o tal vez no exista) un algoritmo eficiente que los resuelva
Lenguajesaceptables y decidibles
– Lenguaje decidible: es aquel lenguaje L para el cual existe una máquina de Turing que puede aceptar cualquier cadena wÎL y rechazar cualquier cadena wÏL.
– Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de Turing que puede aceptar cualquier cadena wÎL y rechazar cualquier cadena wÏL.
– Lenguajes recursivamente innumerables: lenguajesestructurados por frases.
– Lenguajes recursivos: lenguajes decidibles por una máquina de Turing
Lenguajes aceptables vs. Lenguajes decidibles
Lenguaje aceptable
La máquina separa al reconocer una cadena
del lenguaje
Lenguaje decidible
La máquina dice si una cadena pertenece allenguaje o no
Implica reconocer el complemento del lenguaje
¡Existen lenguajes aceptables que no son
decidibles!
Un lenguaje es aceptable pero su…