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 que contienen 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 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 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ás corto 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 y entendibles 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 son teó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/o espacio) 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
Lenguajes aceptables 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: lenguajes estructurados 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 al
lenguaje o no
Implica reconocer el complemento del lenguaje
¡Existen lenguajes aceptables que no son
decidibles!
Un lenguaje es aceptable pero su
complemento no.
PROBLEMA DE LA PARADA El problema de parada para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Fue además el primer problema que se demostró formalmente que no tenía solución. El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe un algoritmo que nos permita determinar si el problema tiene solución. Una de las razones por la que es importante conocer que el problema de la parada no tiene solución, es que nos permite decidir si otros problemas son resolubles o no
definicion Sea M una máquina de Turing arbitraria con un alfabeto de entrada Σ. Sea . ¿Puede decidirse si la máquina M se detendrá con la entrada w?
Solución La respuesta a esta pregunta es negativa. No se puede determinar si una máquina de Turing se detiene con una entrada arbitraria.
Demostración Para demostrarlo, supongamos que el problema de la parada tiene solución, es decir, supondremos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing para con una entrada determinada.
Consideremos una máquina de Turing P, que recibe como entrada una máquina de Turing M y una cadena w codificadas en la cinta y una a continuación de la otra (Mw), y que se encarga de ejecutar M sobre la cadena w. La máquina P parará y aceptará la entrada si M para con w, y parará y rechazará la entrada si M no para con w.
Modificamos la máquina P, creando una máquina P’ equivalente. Esta máquina no parará si M para con w, y parará si M no para con w.
Ahora crearemos una máquina D, cuya función es la siguiente. Recibe una máquina M, la pasa por una máquina que se encarga de copiar la máquina M a continuación. Por lo tanto, a la salida de la máquina copia, la cinta contendrá MM (la codificación de la máquina repetida). A continuación, D coge este resultado y lo pasa a través de P’. Con esto intentamos decidir si la máquina M para con la entrada M. Es decir, si M para con la entrada M, entonces D no para, y si M no para con la entrada M, entonces D para.
Por último, tomaremos una máquina D (denominaremos SD), y le aplicaremos como entrada una máquina D. SD aplica como entrada a la máquina que recibe, la misma máquina. Por lo tanto, esta máquina en principio parará si D no para con entrada D, y no parará si D para con entrada D. Pero si SD no para y si D para con entrada D, sabiendo que D=SD, llegamos a una contradicción, por que aplicar D a SD debería dar como resultado lo mismo que aplicar D sobre D. Del mismo modo para el otro caso. Por lo tanto, el problema de la parada no tiene solución.
Informacion por Karina Sosa Ramos instituto tecnologico de villahermosa ing. sistemas computacionales
