Teoria de la computacion

Teoría de la computación.
Unidad Temas Subtemas
1 Introducción. 1.1 Autómatas, computabilidad y complejidad.
1.2 Nociones matemáticas.
1.2.1 Conjuntos
1.2.2 Funciones y Relaciones
1.2.3 Cadenas y Lenguajes
1.3 Inducción matemática.
2 Lenguajes regulares. 2.1 Autómatas finitos
2.1.1 Autómatas finitos determinísticos.
2.1.2 Autómatas finitos No determínisticos
2.2 Expresiones regulares.2.3 Lenguajes no regulares.
3 Lenguajes libres de contexto. 3.1 Gramáticas libres de contexto.
3.2 Árboles de derivación.
3.3 Formas normales de Chomsky.
3.4 Formas normales de Greibach.
3.5 Eliminación de Factores Comunes izquierdos.
3.6 Eliminación de recursividad izquierda.
3.7 Eliminación de la ambigüedad.
3.8 Autómatas Push-Down.
3.9 Lenguajes no regulares.
4 Máquina de Turing. 4.1Definición formal de una máquina de Turing.
4.2 Construcción modular de una máquina de Turing.
4.3 Lenguajes aceptados por la MT.
4.4 Variantes de una máquina de Turing.
4.5 Problemas de Hilbert.
5 Decibilidad. 5.1 Lenguajes Decidibles.
5.2 El problemas de Halting.
5.3 Decidibilidad de Teorías Lógicas.
6 Reducibilidad. 6.1 Problemas insolubles para la teoría de lenguajes.
6.2 Un problemasimple insoluble.
6.3 Funciones computables.
6.4 Reducibilidad de Turing.

Unidad 1
Introducción.

1.1 Autómatas, computabilidad y complejidad.
Los autómatas vienen a ser mecanismos formales que ``realizan'' derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generada en una gramática si y sólo si la palabra hacetransitar al autómata correspondiente a sus condiciones terminales. Por esto es que los autómatas son analizadores léxicos (llamados en inglés ``parsers'') de las gramáticas a que corresponden.

En matemáticas, la veracidad de una proposición queda asentada sólo cuando se la demuestra. Para aceptar una proposición cuantificada universalmente, es decir, de la forma ``Todo x cumple '', esinsuficiente demostrar que para algunos posibles ``testigos'' se ha probado que efectivamente se cumple , con , por muy grande que sea N, pues aunque haya evidencia de que muchos puntos satisfacen al predicado , ésta no basta para concluir que ``todos'' los puntos lo satisfacen. Dos maneras típicas de demostrar proposiciones cuantificadas universalmente son los razonamientos por contradicción y, cuandoel conjunto de puntos es numerable, por inducción. Las primeras dos secciones de este capítulo se abocan a la presentación de esos métodos de demostración. Posteriormente presentamos los métodos de Cantor para mostrar como numerables a los productos finitos de conjuntos numerables. Esto es de particular importancia en la Teoría de la Complejidad pues permite construir una enumeración efectiva delos ``programas'' en un esquema de programación que sea efectivamente ``computable''. Como una primera aproximación a la noción de ``computabilidad'' presentamos a los programas-while como un lenguaje formal de programación, con sintaxis y semántica bien definidos, y, finalmente, a través de ellos introducimos la noción de funciones computables. Introducimos, luego, a las máquinas de Turing . Talesmáquinas aportan un enfoque alternativo al concepto de ``computabilidad'', sin embargo es equivalente al anterior. Probada esa equivalencia, terminaremos de presentar, de manera introductoria, a las funciones computables. Posteriormente, enunciamos la tesis de Church . A las funciones computables es posible presentarlas también como elementos de clases mínimas de funciones que contienen a uncierto conjunto de funciones y que son cerradas bajo algunos esquemas de composición. De tales enfoques nos ocuparemos en este primer capítulo. Finalmente, veremos que la clase de programas formales, la de las máquinas de Turing y la de las funciones computables son todas numerables. Dado que la clase de todas las funciones posee la misma cardinalidad de los números reales tenemos inmediatamente...