Teoría de la Computación

Indice

Unidad  1 Introduccion teoria de la computacion

1.1 Automatas, Computabilidad y Complejidad

1.2 Nociones Matematicas de Teoria de la Computacion

1.2.1 Conjuntos Tc

1.2.2 Funciones Y Relaciones TC

1.2.3 Cadenas y Lenguajes

1.3 Induccion Matematica

Unidad 2 Lenguajes Regulares

2.1 Automatas Finitos

2.1.1 Automatas Finitos Deterministicos

2.1.2 Automatas Finitos no Deterministicos

2.2 Expresiones Regulares

2.3 Lenguajes no Regulares

Unidad 3 Lenguajes Libres de contexto

3.1 Gramaticas Libres de Contexto

3.2 Arboles de Derivacion

3.3 Formas Normales de Chomsky

3.4 Formas Normales de Greibach

3.5 Eliminacion de Factores Comunes Izquierdos

3.6 Eliminacion Recursividad Izquierda

3.7 Eliminacion De Ambiguedad

3.8 Automatas PushDown

3.9 Lenguajes no Regulares

Unidad 4 Maquina de Turing

4.1 Definicion Formal Maquina de Turing

4.2 Construccion Modular Maquina de Turing

4.3 Lenguajes aceptados por Maquina de Turing

4.4 Variantes Maquina de Turing

4.5 Problemas de Hilbert

Unidad 5 Decibilidad

5.1 Lenguajes Decidibles

5.2 El Problemas de Halting

5.3 Decidibilidad Teorias Logicas

Unidad 6 Reducibilidad

6.1 Problemas Insolubles Teoria de Lenguajes

6.2 Un Problema simple Insoluble

6.3 Funciones Computables

6.4 Reducibilidad De Turing

Introducción

La teoría de la computación es una ciencia, en particular una rama de la matemática y de la computación que centra su interés en el estudio y definición formal de los cómputos.

Se le llama cómputo a la obtención de una solución o resultado (generalmente en el sentido matemático/aritmético del término), a partir de ciertos datos o entradas utilizando para ello un proceso o algoritmo.

Historia

Desde épocas antiguas el hombre ha tenido la necesidad de contar y/o calcular, el contador era el hombre, el computador, y se efectuaban los cómputos de manera mental o asistida por rudimentos como cuentas, lápiz y papel, o tablas.

Los antecedentes de la computación mecánica, pueden trazarse hasta épocas antiguas, con el desarrollo de artefactos para asistir el proceso de los cálculos matemáticos mentales, por ejemplo el ábaco, la regla de cálculo o el quipu.

Aunque quizás sea más propicia como ejemplo precursor, la célebre calculadora griega de Antikythera, utilizada según los expertos para asistir en cálculos astronómicos, y considerada por muchos como la primera computadora.

El Abaco

Quizás fue el primer dispositivo mecánico de contabilidad que existió. Se ha calculado que tuvo su origen hace al menos 5000 años y su efectividad ha soportado la prueba del tiempo.

La Pascalina

El inventor y pintor Leonardo Da Vinci (1452-1519) trazó las ideas para una sumadora mecánica. Siglo y medio después, el filósofo y matemático francés Blaise Pascal (1623-1662) inventó y construyó la primera sumadora mecánica. Se le llamo Pascalina y funcionaba como maquinaria a base de engranajes y ruedas. A pesar de que Pascal fue enaltecido por toda Europa debido a sus logros, la Pascalina, resultó un desconsolador fallo financiero, pues para esos momentos, resultaba más costosa que la labor humana para los cálculos aritméticos.

Máquinas sumadoras como la de Blaise Pascal son aparatos que demuestran una notable pericia de sus creadores en el conocimiento sobre la forma de elaborar los cálculos deseados, al grado de poder representarlos en la forma de mecanismos más o menos elaborados.

La primera máquina de calcular mecánica, un precursor del ordenador digital, fue inventada en 1642 por el matemático francés Blaise Pascal. Aquel dispositivo utilizaba una serie de ruedas de diez dientes en las que cada uno de los dientes representaba un dígito del 0 al 9. Las ruedas estaban conectadas de tal manera que podían sumarse números haciéndolas avanzar el número de dientes correcto. En 1670 el filósofo y matemático alemán Gottfried Wilhelm Leibniz perfeccionó esta máquina e inventó una que también podía multiplicar.

El inventor francés Joseph Marie Jacquard, al diseñar un telar automático, utilizó delgadas placas de madera perforadas para controlar el tejido utilizado en los diseños complejos. Durante la década de 1880 el estadístico estadounidense Herman Hollerith concibió la idea de utilizar tarjetas perforadas, similares a las placas de Jacquard, para procesar datos. Hollerith consiguió compilar la información estadística destinada al censo de población de 1890 de Estados Unidos mediante la utilización de un sistema que hacía pasar tarjetas perforadas sobre contactos eléctricos.

La máquina analítica

También en el siglo XIX el matemático e inventor británico Charles Babbage elaboró los principios de la computadora digital moderna. Inventó una serie de máquinas, como la máquina diferencial, diseñadas para solucionar problemas matemáticos complejos. Muchos historiadores consideran a Babbage y a su socia, la matemática británica Augusta Ada Byron (1815-1852), hija del poeta inglés Lord Byron, como a los verdaderos inventores de la computadora digital moderna. La tecnología de aquella época no era capaz de trasladar a la práctica sus acertados conceptos; pero una de sus invenciones, la máquina analítica, ya tenía muchas de las características de un ordenador moderno. Incluía una corriente, o flujo de entrada en forma de paquete de tarjetas perforadas, una memoria para guardar los datos, un procesador para las operaciones matemáticas y una impresora para hacer permanente el registro.

Sin embargo, la teoría de la computación como ciencia comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas.

En ese época varios matemáticos se preguntaban qué clase de problemas de la matemática, podían resolverse por “métodos simples” y cuales no. Y para ello debían en principio desarrollar una definición de “método para resolver problemas”, es decir, necesitaban el desarrollo de una noción formal (matemática) de lo que es un cálculo/algoritmo y la aritmética lógica.

Durante el siglo XIX y XX diversas corrientes filosóficas allanaron el camino de la computación a partir de las definiciones de sistemas formales. Destacando Kurt Gödel y Bertrand Russell entre otros.

Varias definiciones y modelos formales de lo que es un cálculo fueron propuestos por precursores del dominio como Alan Turing y Alonzo Church; entre esos modelos están la máquina de Turing, las funciones recursivas, y el cálculo Lambda. Todos los cuales se ha demostrado posteriormente que son equivalentes en expresividad computacional, es decir, todos pueden representar la misma clase de cómputos o algoritmos, aunque lo hagan de maneras diferentes.

Se asume normalmente que las computadoras electrónicas son también equivalentes en capacidad de cómputo a cualquiera de esos tres modelos mencionados anteriormente, pero no existe una prueba formal de ello, por tal razón a tal presunción razonable se le conoce como la conjetura de Church-Turing.

De allí la relevancia del estudio de las máquinas de Turing, pues gracias a tal conjetura ampliamente aceptada como verdadera, todo problema de cómputo que sea resoluble en una máquina de Turing, se considera que también lo será en una computadora, y viceversa.

Es meritorio el hecho que gracias a la equivalencia de máquinas de Turing y computadoras, se haya determinado que existen cálculos que no pueden ser resueltos en un tiempo razonable en ninguna computadora imaginable, o incluso, que no pueden resolverse en lo absoluto, por ejemplo el problema de correspondencia de Post o el problema de predecir si una máquina de Turing cualquiera va a llegar a un estado final (conocido como el problema del halting en inglés, o problema de la parada).

Otros temas de interés de la teoría de la computación, son la cantidad de tiempo o la cantidad de memoria necesaria para realizar un cálculo dado. Se ha determinado que existen cómputos resolubles, pero que necesitan cantidades irrealistas de tiempo o memoria para poder efectuarse. Es sumamente importante para los especialistas del dominio conocer la complejidad computacional de un algoritmo, pues ésta determinará la aplicabilidad del mismo.

Otro interés de esta ciencia, son los modelos reducidos de cómputo, que son en realidad casos particulares de una máquina de Turing. Como lo son las máquinas de estado finito esbozadas primero por Warren McCulloch y Walter Pitts en 1943, y los autómatas con pila.

Concepto de Computación

El concepto “computación” se refiere al estudio científico que se desarrolla sobre sistemas automatizados de manejo de información, lo cual se lleva a cabo a través de herramientas pensadas para tal propósito. Es de este modo, que aparecen conceptos como Tecnologías de la Informática, las cuales se vinculan entre sí en el marco del procesamiento y movilidad de la información.

Las Ciencias de la Computación supone un área muy profundo de análisis, que tiene sus orígenes en 1920, cuando “computación” hacía referencia a los cálculos generados por la propia persona. Luego, con la llegada de las computadoras mecánicas, sustituyendo en los cálculos o cómputos a la persona, la historia y el significado de este concepto se ampliaría sobre nuevos horizontes, distinguiendo los algoritmos que forman parte del desarrollo de las soluciones.

En resumen, “computación” implica las órdenes y soluciones dictadas en una máquina, por ejemplo un PC, comprendiendo el análisis de los factores involucrados sobre este proceso, dentro de los cuales aparecen los lenguajes de programación. De este modo, se automatizan tareas, generando datos concretos de forma ordenada y estructurada.

Disciplinas

La teoría de la computación tiene varias disciplinas propias, entre ellas:

• La Teoría de los lenguajes y gramáticas formales, que es el estudio y procesamiento de lenguajes artificiales, a través de la utilización de modelos simplificados de cómputo, como son las autómatas finitos y los autómatas de pila.

• La complejidad, o el estudio de la cantidad de tiempo y de espacio en memoria que toma la ejecución de un cómputo dado.

• La Teoría de la computabilidad, o el estudio y determinación de la clase de problemas que pueden ser resueltos en una máquina de Turing.