unidad 5 y 6 teoria de la computaciom



MATERIA:
TEORIA DE LA COMPUTACION.

PROFESOR:
ARMANDO BECERRA DEL ANGEL

ING. SISTEMAS COMPUTACIONALES

ALUMNO:
EDGAR IGNACIO HERNANDEZ MORALES

NO. CONTROL:
09070936



UNIDAD 5:Decibilidad
En el desarrollo del siguiente trabajo abordaremos temas como Lenguajes decidibles los problemas de Halting, y a decibilidad de teorías lógicas los cuales nospermitirán reforzar nuestros conocimientos en el área de Lenguajes y teoría de autómatas, además el contenido nos permitirá profundizar en el tema de la maquina de Turing abordando diferentes aspectos de los comportamientos que se nos podrían presentar en el desarrollo de un autómata o de una maquina de Turing.

5.1 Lenguajes Decidibles
 Existen problemas que no pueden ser resueltos por unacomputadora, 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 computabilidad tiene como objetivo el estudio de problemas de decisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemasse 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 Mtermina 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 alfabeto sería, ababba.
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
Las frasessobre 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 cortó entre esos dos vértices.
Las frases que describen una máquina deTuring 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
1. La máquina dice si una cadena pertenece al lenguaje o no.
2. Implica reconocer el complemento del lenguaje.
3. Existen lenguajes aceptables que no son decidibles,
4. Un lenguaje es aceptable pero su complemento no.


Una MT de este tipo secorresponde 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 un lenguaje recursivo, y se dice que es indecidible si no es un lenguaje recursivo.
La existencia o no existencia de un algoritmo pararesolver 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, por lo que en cierto sentido no “resuelven el problema”. Por tanto, dividir los problemas entre los lenguajes decidibles (aquellos quese resuelven mediante un algoritmo) e indecidibles, a menudo es mas importante que la división entre lenguajes recursivamente e numerables (aquellos para los que existen maquinas de Turing de alguna clase) y lenguajes no recursivamente e numerables (aquellos para los que no existe ninguna MT).relación entre estas tres clases de lenguajes.
Los lenguajes recursivos
Los lenguajes que no son...