Autómatas, computabilidad y complejidad

La teoría de la compatibilidad, también denominada teoría de la recursión, es una de las cuatro partes que constituyen la lógica matemática, siendo las otras tres, la teoría de conjuntos, la teoría de modelos y la teoría de la demostración, y se ocupa del estudio y clasificación de las relaciones y aplicaciones computables. Además, la teoría de la computabilidad, complejidad computacional, juntocon la teoría de autómatas, lenguajes y máquinas, es el fundamento de la informática teórica y esta, a su vez, de la industria de los ordenadores.

La teoría de autómatas es una rama de las ciencias de la computación que estudia matemáticamente máquinas abstractas y problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguajeformal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata es un modelo matemático para una máquina de estado finita, es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla), esta función de transición dice alautómata a que estado cambiar dados un determinado estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en esta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.
Dependiendodel estado en el que el autómata para se dice que este ha aceptado o rechazado la entrada. Si este termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Autómata del griego automatos, que significa espontáneo o conmovimiento propio, puede referirse a:
• Autómata programable: Equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales.
• Teoría de autómatas: Estudio matemático de máquinas abstractas (autómata finito, autómata con pila).
• Autómata (mecánico): Máquina que imita la figura y los movimientos de un seranimado.
• Robot: Máquina o ingenio electrónico programable, capaz de manipular objetos y realizar operaciones antes reservadas solo a las personas.

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de Turing?
• ¿Qué problemas requieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?
El origen de los modelos abstractos de computación se encuadra en los años 30 (antes de que existieran los ordenadores modernos), para el trabajo de los lógicos AlonzoChurch, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iníciales han tenido una profunda influencia, tanto en el desarrollo teórico como en abundantes aspectos de la práctica de la computación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajespor estructuras formales basados en reglas de producción.
El punto inicial de estos primeros trabajos fueron las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de un congreso internacional.
Lo que Hilbert pretendía era crear un sistema matemático formal completo y consistente en el cual, todas las aseveraciones fueran planteadas con precisión. Su intención...