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 se ocupa de qué problemas se pueden resolver sobre un modelo de computación, usando un algoritmo, qué tan eficientemente se pueden resolver o en qué grado (por ejemplo, soluciones aproximadas versus 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?".

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. Los científicos informáticos estudian la máquina de Turing porque es simple de formular, puede analizarse y usarse para probar resultados, y porque representa lo que muchos consideran el modelo de computación "razonable" más poderoso posible (ver la tesis de Church-Turing). Podría parecer que la capacidad de memoria potencialmente infinita es un atributo irrealizable, pero cualquier problema decidibleresuelto 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 lo tanto, se utilizan las matemáticas y la lógica. En el siglo pasado se convirtió en una disciplina académica independiente y se separó de las matemáticas.

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 los autómatas

Gramática	Idiomas	Autómata	Reglas de producción (restricciones)
Tipo-0	enumerable recursivamente	máquina de Turing	(sin restricciones)
Tipo 1	sensible al contexto	Máquina de Turing no determinista de límites lineales
Tipo 2	Sin contexto	Autómata pushdown no determinista
Tipo-3	Regular	Autómata de estado finito	y

La teoría de autómatas es el estudio de máquinas abstractas (o más apropiadamente, máquinas o sistemas 'matemáticos' abstractos) y los problemas computacionales que pueden resolverse usando estas máquinas. Estas máquinas abstractas se llaman autómatas. Autómata proviene de la palabra griega (Αυτόματα) que significa que algo está haciendo algo por sí mismo. La teoría de los autómatas también está estrechamente relacionada con la teoría del lenguaje formal, 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 máquinas informáticas y se utilizan para pruebas sobre computabilidad.

Teoría del lenguaje formal

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 relacionado con la teoría de los autómatas, ya que los autómatas se utilizan para generar y reconocer lenguajes formales. Hay varias clases de lenguajes formales, cada uno de los cuales permite especificaciones de lenguaje más complejas que el anterior, es decir, la jerarquía de Chomsky, y cada uno corresponde a una clase de autómatas que lo reconoce. Debido a 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 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 se puede resolver en una computadora. La afirmación de que el problema de la detención no puede resolverse con una máquina de Turing 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 con una máquina de Turing. Gran parte de la teoría de la computabilidad se basa en el resultado del problema de 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.

La teoría de la computabilidad está estrechamente relacionada con la rama de la lógica matemática llamada teoría de recursión, que elimina la restricción de estudiar solo modelos de computación que son reducibles al modelo de Turing. 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 considera no solo si un problema se puede resolver en una computadora, sino también qué tan eficientemente se puede resolver el problema. Se consideran dos aspectos principales: la complejidad del tiempo y la complejidad del espacio, 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 determinado 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 en particular en una larga lista de números se vuelve más difícil a medida que la lista de números crece. 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. Entonces decimos que para resolver este problema, la computadora necesita realizar un número 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 es 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. Entonces, en nuestro ejemplo anterior, podríamos decir que el problema requiere pasos para resolverlo.

Quizás el problema abierto más importante en toda la informática es la cuestión de si una cierta clase amplia de problemas denotados NP se puede resolver de manera eficiente. Esto se discute más en las 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 dada por el ganador del Premio Turing Stephen Cook.

Modelos de computación

Además de una máquina de Turing, se utilizan otros modelos de computación equivalentes (ver: tesis de Church-Turing).cálculo lambdaUn cálculo consiste en 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 combinatoriaes un concepto que tiene muchas similitudes con -calculus, pero también existen diferencias importantes (por ejemplo, el combinador de punto fijo Y tiene forma normal en lógica combinatoria pero no en -calculus). 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 (clarificando así su papel en las matemáticas).funciones μ-recursivasun cálculo consta de una función mu-recursiva, es decir, su secuencia de definición, cualquier valor de entrada y una secuencia de funciones recursivas que aparecen en la secuencia de definición con entradas y salidas. Así, 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 las entradas anteriores mediante el uso de composición, recursión primitiva o recursión μ. Por ejemplo, si , entonces para que aparezca 'f(5)=3', términos como 'g(5)=6' y 'h(5,6)=3' deben aparecer arriba. El cálculo termina solo si el término final da el valor de la función recursiva aplicada a las entradas.Algoritmo de Markovun sistema de reescritura de cadenas que utiliza reglas similares a la gramática para operar en cadenas de símbolos.Registrar maquinaes una idealización teóricamente interesante de una computadora. Hay varias variantes. En la mayoría de ellos, 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 almacén externo infinito (o que crece dinámicamente) (visto en las máquinas de Turing) puede entenderse reemplazando su función 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, un secuencia, o una matriz, etc.) por un gran número natural apropiado: la falta de ambigüedad tanto de la representación como de la interpretación se puede establecer 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 del lenguaje de programación. Los autómatas pushdown 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.

Diferentes modelos de computación tienen la capacidad de realizar diferentes tareas. Una forma de medir el poder de un modelo computacional es estudiar la clase de lenguajes formales que puede generar el modelo; de tal manera se obtiene la jerarquía de lenguajes de Chomsky.