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?".[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 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 ). [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. 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.
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 .
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 utilizando 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 , [5] ya que los autómatas a menudo se clasifican por la clase de lenguajes formales que son capaces de 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.
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 una especificación de lenguaje más compleja que la anterior, es decir, la jerarquía de Chomsky , [6] 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.
