Teoria de la comutacion

CONTENIDO

PORTADA
CONTENIDO
INTRODUCCION
OBJETIVOS

LENGUAJES DECIDIBLES

 Lenguajes Decidibles.

 El problema de Halting.

 Decidibilidad de Teorías Lógicas.

REDUCIBILIDAD

 Problemas insolubles para la teoría de lenguajes.

 Un problema simple insoluble.

 Funciones computables.

 Reducibilidad de Turing.

CONCLUCION

INTRODUCCION

En el presentedocumento se hablara, sobre leguajes dicidibles que 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.

Al mismo tiempo se abordaran otros temas, como son: reducibilidad, funciones computables, reducibilidad de turinng y problemas insolubles para la teoría de lenguajes, donde en algunos textos no se mencionanejemplos o definiciones por qué no la ay.



OBJETIVOS

 Entender y comprender más cada uno de los temas investigados; porque con ello me permitirá incrementar el acervo de mis conocimientos y en un futuro aplicarlos en la vida laboral, con mayor seguridad.

 Dominar cada uno de los conceptos más esenciales de cada tema, una vez investigados en diferentes páginas web y contrastadas con loexpuesto en el grupo de discusión.

 Acreditar el 50% de la unidad con el presente documento.

LENGUAJES DECIDIBLES

DEFINICION: Lenguaje decidible es aquel lenguaje L para el cual existe una máquina de Turing que Puede aceptar cualquier cadena w y 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 aceptarcualquier cadena w y L y rechazar cualquier cadena w ó L.

Lenguajes recursivos: Son lenguajes decidiblles por una máquina de Turing.

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 incluye esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolosque, 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ónexpresados 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 dosvé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 cualquierinstancia 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. 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 sepueden 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...