Teoría de la computación

En informática teórica y matemáticas , la teoría de la computación es la rama que estudia qué problemas se pueden resolver en un modelo de computación, utilizando un algoritmo , con qué eficiencia se pueden resolver o en qué grado (por ejemplo, soluciones aproximadas frente a soluciones precisas). El campo se divide en tres ramas principales: teoría de autómatas y lenguajes formales , teoría de la computabilidad y teoría de la complejidad computacional , que están vinculadas por la pregunta: "¿Cuáles son las capacidades y limitaciones fundamentales de las computadoras?". ^[1]

Para realizar un estudio riguroso de la computación, los científicos informáticos trabajan con una abstracción matemática de las computadoras llamada modelo de computación . Hay varios modelos en uso, pero el más comúnmente examinado es la máquina de Turing . ^[2] Los científicos informáticos estudian la máquina de Turing porque es fácil de formular, se puede analizar y utilizar para demostrar resultados, y porque representa lo que muchos consideran el modelo "razonable" más poderoso posible de computación (véase la tesis de Church-Turing ). ^[3] Puede parecer que la capacidad de memoria potencialmente infinita es un atributo irrealizable, pero cualquier problema decidible ^[4] resuelto por una máquina de Turing siempre requerirá solo una cantidad finita de memoria. Entonces, en principio, cualquier problema que pueda ser resuelto (decidido) por una máquina de Turing puede ser resuelto por una computadora que tenga una cantidad finita de memoria.

Historia

La teoría de la computación puede considerarse la creación de modelos de todo tipo en el campo de la informática. Por ello, se utilizan las matemáticas y la lógica . En el siglo pasado, se separó de las matemáticas y se convirtió en una disciplina académica independiente con sus propias conferencias como la FOCS en 1960 y la STOC en 1969, y sus propios premios como la Medalla Ábaco de la IMU (establecida en 1981 como Premio Rolf Nevanlinna), el Premio Gödel , establecido en 1993, y el Premio Knuth , establecido en 1996.

Algunos pioneros de la teoría de la computación fueron Ramon Llull , Alonzo Church , Kurt Gödel , Alan Turing , Stephen Kleene , Rózsa Péter , John von Neumann y Claude Shannon .

Sucursales

Teoría de autómatas

La teoría de autómatas es el estudio de las máquinas abstractas (o, más apropiadamente, de máquinas o sistemas "matemáticos" abstractos) y de los problemas computacionales que pueden resolverse utilizando estas máquinas. Estas máquinas abstractas se denominan autómatas. Autómata proviene de la palabra griega (Αυτόματα) que significa que algo está haciendo algo por sí mismo. La teoría de autómatas también está estrechamente relacionada con la teoría del lenguaje formal , ^[5] ya que los autómatas a menudo se clasifican por la clase de lenguajes formales que pueden reconocer. Un autómata puede ser una representación finita de un lenguaje formal que puede ser un conjunto infinito. Los autómatas se utilizan como modelos teóricos para las máquinas de computación y se utilizan para pruebas sobre computabilidad.

Teoría del lenguaje formal

La jerarquía de Chomsky — Inclusiones de conjuntos descritas por la jerarquía de Chomsky

La teoría del lenguaje es una rama de las matemáticas que se ocupa de describir los lenguajes como un conjunto de operaciones sobre un alfabeto . Está estrechamente vinculada con la teoría de autómatas, ya que los autómatas se utilizan para generar y reconocer lenguajes formales. Hay varias clases de lenguajes formales, cada una de las cuales permite una especificación del lenguaje más compleja que la anterior, es decir, la jerarquía de Chomsky ^[6] , y cada una corresponde a una clase de autómatas que la reconoce. Debido a que los autómatas se utilizan como modelos para la computación, los lenguajes formales son el modo preferido de especificación para cualquier problema que deba calcularse.

Teoría de la computabilidad

La teoría de la computabilidad se ocupa principalmente de la cuestión de hasta qué punto un problema es solucionable en un ordenador. La afirmación de que el problema de la detención no puede resolverse con una máquina de Turing ^[7] es uno de los resultados más importantes de la teoría de la computabilidad, ya que es un ejemplo de un problema concreto que es fácil de formular e imposible de resolver utilizando una máquina de Turing. Gran parte de la teoría de la computabilidad se basa en el resultado del problema de la detención.

Otro paso importante en la teoría de la computabilidad fue el teorema de Rice , que establece que para todas las propiedades no triviales de las funciones parciales, es indecidible si una máquina de Turing calcula una función parcial con esa propiedad. ^[8]

La teoría de la computabilidad está estrechamente relacionada con la rama de la lógica matemática llamada teoría de la recursión , que elimina la restricción de estudiar solo modelos de computación que sean reducibles al modelo de Turing. ^[9] Muchos matemáticos y teóricos computacionales que estudian la teoría de la recursión se referirán a ella como teoría de la computabilidad.

Teoría de la complejidad computacional

La teoría de la complejidad no solo considera si un problema se puede resolver en una computadora, sino también con qué eficiencia se puede resolver. Se consideran dos aspectos principales: la complejidad temporal y la complejidad espacial, que son respectivamente cuántos pasos se necesitan para realizar un cálculo y cuánta memoria se requiere para realizar ese cálculo.

Para analizar cuánto tiempo y espacio requiere un algoritmo dado , los científicos informáticos expresan el tiempo o el espacio necesarios para resolver el problema como una función del tamaño del problema de entrada. Por ejemplo, encontrar un número particular en una lista larga de números se vuelve más difícil a medida que la lista de números se hace más grande. Si decimos que hay n números en la lista, entonces si la lista no está ordenada o indexada de ninguna manera, es posible que tengamos que mirar cada número para encontrar el número que estamos buscando. Por lo tanto, decimos que para resolver este problema, la computadora necesita realizar una cantidad de pasos que crece linealmente en el tamaño del problema.

Para simplificar este problema, los científicos informáticos han adoptado la notación Big O , que permite comparar funciones de una manera que garantiza que no sea necesario considerar aspectos particulares de la construcción de una máquina, sino solo el comportamiento asintótico a medida que los problemas se hacen más grandes. Por lo tanto, en nuestro ejemplo anterior, podríamos decir que el problema requiere pasos para resolverse. $O(n)$

Tal vez el problema abierto más importante en toda la ciencia informática es la cuestión de si una cierta clase amplia de problemas denominados NP se pueden resolver de manera eficiente. Esto se analiza con más detalle en Clases de complejidad P y NP , y el problema P versus NP es uno de los siete problemas del Premio del Milenio establecidos por el Instituto de Matemáticas Clay en 2000. La descripción oficial del problema fue proporcionada por el ganador del premio Turing Stephen Cook .

Modelos de computación

Aparte de la máquina de Turing , se utilizan otros modelos de computación equivalentes (véase: tesis de Church-Turing ).

Cálculo lambda: Un cálculo consta de una expresión lambda inicial (o dos si desea separar la función y su entrada) más una secuencia finita de términos lambda, cada uno deducido del término anterior mediante una aplicación de reducción Beta .
Lógica combinatoria: es un concepto que tiene muchas similitudes con el cálculo numérico, pero también existen diferencias importantes (por ejemplo, el combinador de punto fijo Y tiene forma normal en lógica combinatoria pero no en cálculo numérico). La lógica combinatoria se desarrolló con grandes ambiciones: comprender la naturaleza de las paradojas, hacer que los fundamentos de las matemáticas sean más económicos (conceptualmente), eliminar la noción de variables (aclarando así su papel en las matemáticas). ${\estilo de visualización \lambda}$ ${\estilo de visualización \lambda}$
Funciones μ-recursivas: un cálculo consiste en una función mu-recursiva, es decir , su secuencia definitoria, cualquier valor de entrada y una secuencia de funciones recursivas que aparecen en la secuencia definitoria con entradas y salidas. Por lo tanto, si en la secuencia definitoria de una función recursiva aparecen las funciones y , entonces podrían aparecer términos de la forma 'g(5)=7' o 'h(3,2)=10'. Cada entrada en esta secuencia debe ser una aplicación de una función básica o seguir de las entradas anteriores mediante composición , recursión primitiva o recursión μ . Por ejemplo, si , entonces para que aparezca 'f(5)=3', deben aparecer términos como 'g(5)=6' y 'h(5,6)=3' arriba. El cálculo termina solo si el término final da el valor de la función recursiva aplicada a las entradas. ${\estilo de visualización f(x)}$ ${\estilo de visualización g(x)}$ $h(x,y)$ $f(x)=h(x,g(x))$
Algoritmo de Markov: un sistema de reescritura de cadenas que utiliza reglas similares a la gramática para operar en cadenas de símbolos.
Registrar máquina: es una idealización teóricamente interesante de un ordenador. Hay varias variantes. En la mayoría de ellas, cada registro puede contener un número natural (de tamaño ilimitado), y las instrucciones son simples (y pocas en número), por ejemplo, solo existe la decrementación (combinada con el salto condicional) y el incremento (y la detención). La falta del almacenamiento externo infinito (o de crecimiento dinámico) (visto en las máquinas de Turing) se puede entender reemplazando su papel con las técnicas de numeración de Gödel : el hecho de que cada registro contenga un número natural permite la posibilidad de representar una cosa complicada (por ejemplo, una secuencia o una matriz, etc.) por un número natural apropiadamente grande; la falta de ambigüedad tanto de la representación como de la interpretación se puede establecer mediante los fundamentos teóricos de números de estas técnicas.

Además de los modelos computacionales generales, algunos modelos computacionales más simples son útiles para aplicaciones especiales y restringidas. Las expresiones regulares , por ejemplo, especifican patrones de cadenas en muchos contextos, desde software de productividad de oficina hasta lenguajes de programación . Otro formalismo matemáticamente equivalente a las expresiones regulares, los autómatas finitos se utilizan en el diseño de circuitos y en algunos tipos de resolución de problemas. Las gramáticas libres de contexto especifican la sintaxis del lenguaje de programación. Los autómatas de inserción no deterministas son otro formalismo equivalente a las gramáticas libres de contexto. Las funciones recursivas primitivas son una subclase definida de las funciones recursivas.

Los distintos modelos de computación tienen la capacidad de realizar distintas tareas. Una forma de medir la potencia de un modelo computacional es estudiar la clase de lenguajes formales que el modelo puede generar; de esta forma se llega a la jerarquía de lenguajes de Chomsky .

Referencias

^ Michael Sipser (2013). Introducción a la teoría de la computación 3.° grado . Cengage Learning. ISBN 978-1-133-18779-0. áreas centrales de la teoría de la computación: autómatas, computabilidad y complejidad. (Página 1)
^ Hodges, Andrew (2012). Alan Turing: El enigma (edición del centenario). Princeton University Press . ISBN 978-0-691-15564-7.
^ Rabin, Michael O. (junio de 2012). Turing, Church, Gödel, computabilidad, complejidad y aleatorización: una visión personal.
^ Donald Monk (1976). Lógica matemática . Springer-Verlag. ISBN 9780387901701.
^ Hopcroft, John E. y Jeffrey D. Ullman (2006). Introducción a la teoría de autómatas, lenguajes y computación. 3.ª ed . Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9.
^ Jerarquía de Chomsky (1956). "Tres modelos para la descripción del lenguaje". Teoría de la información, IRE Transactions on . 2 (3). IEEE: 113–124. doi :10.1109/TIT.1956.1056813. S2CID 19519474.
^ Alan Turing (1937). "Sobre números computables, con una aplicación al Entscheidungsproblem". Actas de la London Mathematical Society . 2 (42). IEEE: 230–265. doi :10.1112/plms/s2-42.1.230. S2CID 73712. Consultado el 6 de enero de 2015 .
^ Henry Gordon Rice (1953). "Clases de conjuntos recursivamente enumerables y sus problemas de decisión". Transacciones de la American Mathematical Society . 74 (2). American Mathematical Society: 358–366. doi : 10.2307/1990888 . JSTOR 1990888.
^ Martin Davis (2004). Lo indecidible: Documentos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables (Dover Ed) . Publicaciones de Dover. ISBN 978-0486432281.

Lectura adicional

Libros de texto dirigidos a informáticos

(Hay muchos libros de texto en esta área; esta lista es necesariamente incompleta).

Hopcroft, John E. y Jeffrey D. Ullman (2006). Introducción a la teoría de autómatas, lenguajes y computación . 3.ª ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9 Una de las referencias estándar en el campo.
Linz P (2007). Una introducción al lenguaje formal y los autómatas . Editorial Narosa. ISBN 9788173197819.
Michael Sipser (2013). Introducción a la teoría de la computación (3.ª ed.). Cengage Learning. ISBN 978-1-133-18779-0.
Eitan Gurari (1989). Introducción a la teoría de la computación. Computer Science Press. ISBN 0-7167-8182-4. Archivado desde el original el 7 de enero de 2007.
Hein, James L. (1996) Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1 Una introducción sencilla al campo, apropiada para estudiantes de segundo año de la carrera de informática.
Taylor, R. Gregory (1998). Modelos de computación y lenguajes formales. Nueva York: Oxford University Press. ISBN 978-0-19-510983-2 Un libro de texto de lectura inusual, apropiado para estudiantes de pregrado de nivel superior o estudiantes de posgrado principiantes.
Lewis, FD (2007). Fundamentos de la informática teórica . Un libro de texto que cubre los temas de lenguajes formales, autómatas y gramáticas. El énfasis parece estar puesto en presentar una descripción general de los resultados y sus aplicaciones en lugar de proporcionar pruebas de los resultados.
Martin Davis , Ron Sigal, Elaine J. Weyuker, Computability, complex, and language: fundamentals of theory of computer science , 2.ª ed., Academic Press, 1994, ISBN 0-12-206382-1 . Abarca una gama más amplia de temas que la mayoría de los demás libros introductorios, incluida la semántica de programas y la teoría de la cuantificación . Dirigido a estudiantes de posgrado.

Libros sobre teoría de la computabilidad desde la perspectiva matemática (más amplia)

Hartley Rogers, Jr. (1987). Teoría de funciones recursivas y computabilidad efectiva , MIT Press. ISBN 0-262-68052-1
S. Barry Cooper (2004). Teoría de la computabilidad . Chapman y Hall/CRC. ISBN 1-58488-237-9..
Carl H. Smith , A recursive introduction to the theory of computation , Springer, 1994, ISBN 0-387-94332-3 . Un libro de texto más breve, adecuado para estudiantes de posgrado en Ciencias de la Computación.

Perspectiva histórica

Richard L. Epstein y Walter A. Carnielli (2000). Computabilidad: funciones computables, lógica y fundamentos de las matemáticas, con Computabilidad: una cronología (2.ª ed.) . Wadsworth/Thomson Learning. ISBN 0-534-54644-7..

Enlaces externos

Teoría de la computación en el MIT
Teoría de la computación en Harvard
Lógica de computabilidad: teoría de computación interactiva. La principal fuente web sobre este tema.