Lenguajes Decidibles.
Páginas: 9 (2226 palabras)
Publicado: 23 de mayo de 2012
Unidad V Decibilidad
Lenguajes Decidibles
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. La teoría de compatibilidad tiene como objetivo el estudiode 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. Decimos que un lenguaje L es decidible si L= (M).
Para una maquina de Turing M tal que:
1.-Si w pertenece a L, entonces M acepta (y por lo tanto se para).
2.- Si w no pertenece a L, entonces M termina parándose, aunque nunca llega a un estado de aceptación.
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, {a, b} y una cadena cualquiera sobre este alfabetosería:
ababba.
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 delgrafo y un camino en el grafo que es el camino más cortó 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.
Lenguaje decidible
• La máquina dice si una cadena pertenece al lenguaje o no.
• Implica reconocer el complemento del lenguaje.
• Existenlenguajes aceptables que no son decidibles,
• Un lenguaje es aceptable pero su complemento no.
Una MT de este tipo se corresponde con nuestro concepto informal de “algoritmos”, una secuencia bien definida de pasos que siempre termina y genera una respuesta. Si pensamos en el lenguaje L como en un “problema”, lo que será frecuente, entonces se dice que el problema L es decidible si es unlenguaje recursivo, y se dice que es indecidible si no es un lenguaje recursivo.
La existencia o no existencia de un algoritmo para resolver un problema a menudo tiene más importancia que la existencia de una MT que resuelva el problema. Las maquinas de Turing que no garantizan la parada no pueden proporcionarnos la suficiente información como para concluir que una cadena no pertenece al lenguaje, porlo que en cierto sentido no ³resuelven el problema´. Por tanto, dividir los problemas entre los lenguajes decidibles (aquellos que se resuelven mediante un algoritmo) e indecidibles, a menudo es mas importante que la división entre lenguajes recursivamente enumerables (aquellos para los que existen maquinas de Turing de alguna clase) y lenguajes no recursivamente e numerables (aquellos para losque no existe ninguna MT). relación entre estas tres clases de lenguajes.
Los lenguajes que no son recursivamente e numerables.
Lenguajes recursivos y recursivamente e numerables. Los lenguajes aceptados por la máquina de Turing son recursivamente e numerables (RE) y el subconjunto de los lenguajes RE que son aceptados por una MT que siempre se para se denominan lenguajes recursivos.Decibilidad e indecibilidad. ³Decidible´ es sinónimo de ³Recursivo´, aunque se suele decir que los lenguajes son recursivos y los problemas (que son los lenguajes interpretados como una cuestión) son decidibles. Si un lenguaje no es recursivo, entonces decimos que el problema expresado por dicho lenguaje es indecidible.
Los Problemas de Halting (Indecidible)
El problema de “Halting” es el primer...
Lenguajes Decidibles
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. La teoría de compatibilidad tiene como objetivo el estudiode 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. Decimos que un lenguaje L es decidible si L= (M).
Para una maquina de Turing M tal que:
1.-Si w pertenece a L, entonces M acepta (y por lo tanto se para).
2.- Si w no pertenece a L, entonces M termina parándose, aunque nunca llega a un estado de aceptación.
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, {a, b} y una cadena cualquiera sobre este alfabetosería:
ababba.
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 delgrafo y un camino en el grafo que es el camino más cortó 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.
Lenguaje decidible
• La máquina dice si una cadena pertenece al lenguaje o no.
• Implica reconocer el complemento del lenguaje.
• Existenlenguajes aceptables que no son decidibles,
• Un lenguaje es aceptable pero su complemento no.
Una MT de este tipo se corresponde con nuestro concepto informal de “algoritmos”, una secuencia bien definida de pasos que siempre termina y genera una respuesta. Si pensamos en el lenguaje L como en un “problema”, lo que será frecuente, entonces se dice que el problema L es decidible si es unlenguaje recursivo, y se dice que es indecidible si no es un lenguaje recursivo.
La existencia o no existencia de un algoritmo para resolver un problema a menudo tiene más importancia que la existencia de una MT que resuelva el problema. Las maquinas de Turing que no garantizan la parada no pueden proporcionarnos la suficiente información como para concluir que una cadena no pertenece al lenguaje, porlo que en cierto sentido no ³resuelven el problema´. Por tanto, dividir los problemas entre los lenguajes decidibles (aquellos que se resuelven mediante un algoritmo) e indecidibles, a menudo es mas importante que la división entre lenguajes recursivamente enumerables (aquellos para los que existen maquinas de Turing de alguna clase) y lenguajes no recursivamente e numerables (aquellos para losque no existe ninguna MT). relación entre estas tres clases de lenguajes.
Los lenguajes que no son recursivamente e numerables.
Lenguajes recursivos y recursivamente e numerables. Los lenguajes aceptados por la máquina de Turing son recursivamente e numerables (RE) y el subconjunto de los lenguajes RE que son aceptados por una MT que siempre se para se denominan lenguajes recursivos.Decibilidad e indecibilidad. ³Decidible´ es sinónimo de ³Recursivo´, aunque se suele decir que los lenguajes son recursivos y los problemas (que son los lenguajes interpretados como una cuestión) son decidibles. Si un lenguaje no es recursivo, entonces decimos que el problema expresado por dicho lenguaje es indecidible.
Los Problemas de Halting (Indecidible)
El problema de “Halting” es el primer...
Leer documento completo
Regístrate para leer el documento completo.