Hispanopedia Wiki
Articulo de referencia

Teoría de la computación

En la informática teórica y las matemáticas , la teoría de la computación es la rama que se ocupa de qué problemas pueden resolverse en un modelo de computación utilizando un al...

Hispanopedia WikiContenido en espanolLectura gratuita

En la informática teórica y las matemáticas , la teoría de la computación es la rama que se ocupa de qué problemas pueden resolverse en un modelo de computación utilizando un algoritmo , con qué eficiencia y 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 . Existen varios modelos para este propósito, como la máquina de Turing . [ 2 ] Los científicos informáticos estudian la máquina de Turing porque es sencilla de formular, se puede analizar y usar para demostrar resultados, y porque representa lo que muchos consideran el modelo de computación "razonable" más potente posible (véase la tesis de Church-Turing ). [ 3 ] Podría 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. Así que, 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 lo tanto, 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 FOCS en 1960 y STOC en 1969, y sus propios premios, como la Medalla IMU Abacus (establecida en 1981 como el 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 estudia las máquinas abstractas (o, más apropiadamente, las máquinas o sistemas matemáticos abstractos) y los problemas computacionales que se pueden resolver con ellas. Estas máquinas abstractas se denominan autómatas. El término «autómata» proviene del griego (Αυτόματα), que significa «algo que realiza una acción por sí mismo». La teoría de autómatas también está estrechamente relacionada con la teoría de lenguajes formales [ 5 ] , ya que los autómatas suelen clasificarse según 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 máquinas de computación y para demostrar la computabilidad.

teoría del lenguaje formal

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

La teoría de lenguajes formales 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 estos se utilizan para generar y reconocer lenguajes formales. Existen varias clases de lenguajes formales, cada una de las cuales permite una especificación más compleja que la anterior (por ejemplo, la jerarquía de Chomsky ) [ 6 ] , y cada una corresponde a una clase de autómatas que la reconoce. Dado que los autómatas se utilizan como modelos para la computación, los lenguajes formales son el modo de especificación preferido para cualquier problema que deba ser computado.

teoría de la computabilidad

La teoría de la computabilidad se ocupa principalmente de la cuestión de hasta qué punto un problema puede resolverse mediante una computadora. La afirmación de que el problema de la parada 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 constituye un ejemplo de un problema concreto que es fácil de formular pero imposible de resolver con una máquina de Turing. Gran parte de la teoría de la computabilidad se basa en el resultado del problema de la parada.

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 denominada teoría de la recursión , que elimina la restricción de estudiar únicamente modelos de computación reducibles al modelo de Turing. [ 9 ] Muchos matemáticos y teóricos de la computación que estudian la teoría de la recursión se refieren a ella como teoría de la computabilidad.

Teoría de la complejidad computacional

Una representación de la relación entre clases de complejidad

La teoría de la complejidad computacional no solo considera si un problema puede resolverse en una computadora, sino también con qué eficiencia. Se consideran dos aspectos principales: la complejidad temporal y la complejidad espacial , que se refieren, respectivamente, a la cantidad de pasos necesarios para realizar un cálculo y a la cantidad de memoria requerida para llevarlo a cabo.

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

Para simplificar este problema, los científicos informáticos han adoptado la notación O grande , 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 vuelven grandes. Así que en nuestro ejemplo anterior, podríamos decir que el problema requiereO(norte){\displaystyle O(n)}pasos para resolver.

Quizás el problema abierto más importante en toda la informática sea la cuestión de si una cierta clase amplia de problemas, denominada NP, puede resolverse 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 planteados por el Instituto Clay de Matemáticas en 2000. La descripción oficial del problema fue proporcionada por Stephen Cook, ganador del Premio Turing .

Modelos de computación

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

Cálculo lambda
Un cálculo consiste en una expresión lambda inicial (o dos si se desea separar la función y su entrada) más una secuencia finita de términos lambda, cada uno deducido del término precedente mediante una aplicación de la reducción Beta .
Lógica combinatoria
es un concepto que tiene muchas similitudes conλ{\displaystyle \lambda }-cálculo, pero también existen diferencias importantes (por ejemplo, el combinador de punto fijo Y tiene forma normal en lógica combinatoria pero no enλ{\displaystyle \lambda }-cálculo). La lógica combinatoria se desarrolló con grandes ambiciones: comprender la naturaleza de las paradojas, hacer que los fundamentos de las matemáticas fueran más económicos (conceptualmente), eliminar la noción de variables (aclarando así su papel en las matemáticas).
funciones μ-recursivas
Un cálculo consiste en una función recursiva mu, es decir , su secuencia definitoria, cualquier valor(es) 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 recursivaF(incógnita){\displaystyle f(x)}las funcionesgramo(incógnita){\displaystyle g(x)}yh(incógnita,y){\displaystyle h(x,y)}Aparecen 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 derivarse de las entradas anteriores mediante composición , recursión primitiva o recursión μ . Por ejemplo, siF(incógnita)=h(incógnita,gramo(incógnita)){\displaystyle f(x)=h(x,g(x))}Para que aparezca 'f(5)=3', deben aparecer términos como 'g(5)=6' y 'h(5,6)=3' anteriormente. El cálculo finaliza solo si el último término da el valor de la función recursiva aplicada a las entradas.
algoritmo de Markov
un sistema de reescritura de cadenas que utiliza reglas similares a la gramática para operar sobre cadenas de símbolos.
Máquina registradora
es una idealización teóricamente interesante de una computadora. Hay varias variantes. En la mayoría de ellas, cada registro puede almacenar un número natural (de tamaño ilimitado), y las instrucciones son simples (y pocas), por ejemplo, solo existen la decrementación (combinada con salto condicional) y el incremento (y la parada). La falta de la memoria externa infinita (o de crecimiento dinámico) (que se observa en las máquinas de Turing) puede entenderse reemplazando su función con técnicas de numeración de Gödel : el hecho de que cada registro almacene un número natural permite la posibilidad de representar algo complejo (por ejemplo, una secuencia, una matriz, etc.) mediante un número natural suficientemente grande; la uniambigüedad tanto de la representación como de la interpretación puede establecerse mediante los fundamentos teóricos numéricos 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 de los lenguajes de programación. Los autómatas de pila 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 diferentes tareas. Una forma de medir la potencia de un modelo computacional es estudiar la clase de lenguajes formales que puede generar; de esta manera se obtiene la jerarquía de lenguajes de Chomsky .

Referencias

  1. ↑ Sipser (2013 , p. 1) : 
    "Áreas centrales de la teoría de la computación: autómatas, computabilidad y complejidad."
  2. ↑ Hodges, Andrew (2012). Alan Turing: El enigma (  Edición del centenario). Princeton University Press . ISBN 978-0-691-15564-7.
  3. ↑ Rabin, Michael O. (junio de 2012). Turing, Church, Gödel, Computabilidad, Complejidad y Aleatorización: Una visión personal .
  4. ↑ Donald Monk (1976). Lógica matemática . Springer-Verlag. ISBN 9780387901701.
  5. ↑ 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.
  6. ↑ Chomsky, N. (1956). "Tres modelos para la descripción del lenguaje". IEEE Transactions on Information Theory . 2 (3): 113– 124. Bibcode : 1956IRTIT...2..113C . doi : 10.1109/TIT.1956.1056813 . S2CID 19519474 . 
  7. ↑ Alan Turing (1937). "Sobre los números computables, con una aplicación al problema de decisión" . Actas de la Sociedad Matemática de Londres . 2 (42). IEEE: 230–265 . Bibcode : 1937PLMS...42..230T . doi : 10.1112/plms/s2-42.1.230 . S2CID 73712. Consultado el 6 de enero de 2015 . 
  8. ↑ Henry Gordon Rice (1953). "Clases de conjuntos recursivamente enumerables y sus problemas de decisión" . Transactions of the American Mathematical Society . 74 (2). American Mathematical Society: 358–366 . doi : 10.2307/1990888 . JSTOR 1990888 . 
  9. ↑ Martin Davis (2004). Lo indecidible: Artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables (Edición Dover) . Dover Publications. ISBN 978-0486432281.

Lecturas adicionales

Libros de texto dirigidos a informáticos

(Existen numerosos libros de texto sobre este tema; esta lista es necesariamente incompleta).

  • Hopcroft, John E .; Motwani, Rajeev ; Ullman, Jeffrey D. (2006) [1979]. Introducción a la teoría de autómatas, lenguajes y computación (3.ª  ed.). Addison-Wesley. ISBN 0-321-45536-3.— 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.
  • Sipser, Michael (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-4Archivado del original el 7 de enero de 2007.
  • Hein, James L. (1996) Teoría de la computación. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1Una introducción sencilla al campo, apropiada para estudiantes de segundo año 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 inusualmente fácil de leer, apropiado para estudiantes de último año de licenciatura o estudiantes de posgrado que se inician en la materia.
  • Jon Kleinberg y Éva Tardos (2006): Diseño de algoritmos , Pearson/Addison-Wesley, ISBN 978-0-32129535-4
  • Lewis, FD (2007). Fundamentos de la informática teórica. Un libro de texto que abarca los temas de lenguajes formales, autómatas y gramáticas. El énfasis parece estar en presentar una visión general de los resultados y sus aplicaciones, más que en proporcionar demostraciones de los mismos.
  • Martin Davis , Ron Sigal, Elaine J. Weyuker, Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , 2.ª ed., Academic Press, 1994, ISBN 0-12-206382-1Abarca una gama más amplia de temas que la mayoría de los demás libros introductorios, incluyendo 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 una perspectiva matemática (más amplia)
  • Hartley Rogers, Jr. (1987). Teoría de las funciones recursivas y la computabilidad efectiva , MIT Press. ISBN 0-262-68052-1
  • S. Barry Cooper (2004). Teoría de la computabilidad . Chapman and Hall/CRC. ISBN 1-58488-237-9..
  • Carl H. Smith , Introducción recursiva a la teoría de la computación , Springer, 1994, ISBN 0-387-94332-3Un 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..
  • Teoría de la Computación en el MIT
  • Teoría de la Computación en Harvard
  • Lógica de Computabilidad : una teoría de la computación interactiva. La principal fuente web sobre este tema.