La computabilidad es la capacidad de resolver un problema de manera eficaz. Es un tema clave del campo de la teoría de la computabilidad dentro de la lógica matemática y la teoría de la computación dentro de la informática . La computabilidad de un problema está estrechamente ligada a la existencia de un algoritmo para resolver el problema.
Los modelos de computabilidad más estudiados son las funciones computables de Turing y μ-recursivas , y el cálculo lambda , todos los cuales tienen potencia computacional equivalente. También se estudian otras formas de computabilidad: en la teoría de los autómatas se estudian nociones de computabilidad más débiles que las máquinas de Turing, mientras que en el campo de la hipercomputación se estudian nociones de computabilidad más fuertes que las máquinas de Turing .
Una idea central en computabilidad es la de un problema ( computacional ) , que es una tarea cuya computabilidad puede explorarse.
Hay dos tipos clave de problemas:
Otros tipos de problemas incluyen problemas de búsqueda y problemas de optimización .
Uno de los objetivos de la teoría de la computabilidad es determinar qué problemas, o clases de problemas, pueden resolverse en cada modelo de computación.
Un modelo de computación es una descripción formal de un tipo particular de proceso computacional. La descripción a menudo toma la forma de una máquina abstracta destinada a realizar la tarea en cuestión. Los modelos generales de computación equivalentes a una máquina de Turing (ver tesis de Church-Turing ) incluyen:
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.
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 el modelo puede generar; de esta forma se obtiene la jerarquía de lenguas de Chomsky.
Otros modelos restringidos de cálculo incluyen:
Con estos modelos computacionales en la mano, podemos determinar cuáles son sus límites. Es decir, ¿qué clases de idiomas pueden aceptar?
Los informáticos llaman lenguaje regular a cualquier lenguaje que pueda ser aceptado por una máquina de estados finitos . Debido a la restricción de que el número de estados posibles en una máquina de estados finita es finito, podemos ver que para encontrar un lenguaje que no sea regular, debemos construir un lenguaje que requiera un número infinito de estados.
Un ejemplo de tal lenguaje es el conjunto de todas las cadenas que consisten en las letras 'a' y 'b' que contienen un número igual de letras 'a' y 'b'. Para ver por qué este lenguaje no puede ser reconocido correctamente por una máquina de estados finitos, supongamos primero que dicha máquina M existe. M debe tener algún número de estados n . Ahora considere la cadena x que consta de 'a seguidas de 'b'.
Como M se lee en x , debe haber algún estado en la máquina que se repita como se lee en la primera serie de 'a's, ya que hay 'a's y solo n estados según el principio del casillero . Llame a este estado S y, además, sea d el número de 'a' que nuestra máquina leyó para pasar de la primera aparición de S a alguna aparición posterior durante la secuencia 'a'. Sabemos, entonces, que en esa segunda aparición de S , podemos agregar d (donde ) 'a adicionales y estaremos nuevamente en el estado S. Esto significa que sabemos que una cadena de "a" debe terminar en el mismo estado que la cadena de "a". Esto implica que si nuestra máquina acepta x , también debe aceptar la cadena de 'a seguida de 'b', que no está en el lenguaje de cadenas que contienen un número igual de 'a y 'b'. En otras palabras, M no puede distinguir correctamente entre una cadena con el mismo número de 'a y 'b' y una cadena con 'a y 'b'.
Sabemos, por tanto, que este lenguaje no puede ser aceptado correctamente por ninguna máquina de estados finitos y, por tanto, no es un lenguaje regular. Una forma más general de este resultado se denomina lema de bombeo para lenguajes regulares , que puede usarse para mostrar que una máquina de estados finitos no puede reconocer clases amplias de lenguajes.
Los informáticos definen un lenguaje que puede ser aceptado por un autómata pushdown como lenguaje libre de contexto , que puede especificarse como gramática libre de contexto . El lenguaje que consta de cadenas con igual número de 'a y 'b', que mostramos que no era un lenguaje normal, puede decidirse mediante un autómata push-down. Además, en general, un autómata push-down puede comportarse como una máquina de estados finitos, por lo que puede decidir cualquier lenguaje que sea regular. Por tanto, este modelo de computación es estrictamente más potente que las máquinas de estados finitos.
Sin embargo, resulta que hay idiomas que tampoco pueden ser decididos por un autómata push-down. El resultado es similar al de las expresiones regulares y no se detallará aquí. Existe un lema de bombeo para lenguajes libres de contexto . Un ejemplo de tal lenguaje es el conjunto de números primos.
Las máquinas de Turing pueden decidir cualquier lenguaje libre de contexto, además de los lenguajes que no pueden decidirse mediante un autómata push-down, como el lenguaje que consta de números primos. Por tanto, es un modelo de cálculo estrictamente más potente.
Debido a que las máquinas de Turing tienen la capacidad de "hacer copias de seguridad" en su cinta de entrada, es posible que una máquina de Turing funcione durante mucho tiempo de una manera que no es posible con los otros modelos de cálculo descritos anteriormente. Es posible construir una máquina de Turing que nunca termine de funcionar (se detenga) en algunas entradas. Decimos que una máquina de Turing puede decidir un lenguaje si finalmente se detiene en todas las entradas y da una respuesta. Un lenguaje que puede decidirse así se llama lenguaje recursivo . Podemos describir con más detalle las máquinas de Turing que eventualmente se detendrán y darán una respuesta para cualquier entrada en un idioma, pero que pueden funcionar indefinidamente para cadenas de entrada que no están en el idioma. Estas máquinas de Turing podrían decirnos que una cadena determinada está en el lenguaje, pero es posible que nunca estemos seguros, basándose en su comportamiento, de que una cadena determinada no esté en un lenguaje, ya que en tal caso puede ejecutarse para siempre. Un lenguaje aceptado por una máquina de Turing de este tipo se denomina lenguaje recursivamente enumerable .
Resulta que la máquina de Turing es un modelo de autómata extremadamente poderoso. Los intentos de modificar la definición de máquina de Turing para producir una máquina más potente han fracasado sorprendentemente. Por ejemplo, agregar una cinta adicional a la máquina de Turing y darle una superficie infinita bidimensional (o tridimensional o de cualquier dimensión) para trabajar puede ser simulado por una máquina de Turing con la cinta unidimensional básica. Por tanto, estos modelos no son más potentes. De hecho, una consecuencia de la tesis de Church-Turing es que no existe ningún modelo razonable de computación que pueda decidir lenguajes que no puedan ser decididos por una máquina de Turing.
La pregunta que cabe plantearse entonces es: ¿existen lenguajes que sean recursivamente enumerables, pero no recursivos? Y, además, ¿hay lenguas que ni siquiera son recursivamente enumerables?
El problema de la detención es uno de los problemas más famosos de la informática porque tiene profundas implicaciones en la teoría de la computabilidad y en cómo utilizamos las computadoras en la práctica diaria. El problema se puede formular:
Aquí no estamos haciendo una simple pregunta sobre un número primo o un palíndromo, sino que estamos invirtiendo las tornas y pidiendo a una máquina de Turing que responda una pregunta sobre otra máquina de Turing. Se puede demostrar (Ver artículo principal: Problema de detención ) que no es posible construir una máquina de Turing que pueda responder a esta pregunta en todos los casos.
Es decir, la única forma general de saber con seguridad si un programa determinado se detendrá en una entrada particular en todos los casos es simplemente ejecutarlo y ver si se detiene. Si se detiene, entonces sabes que se detiene. Sin embargo, si no se detiene, es posible que nunca se sepa si eventualmente se detendrá. El lenguaje que consta de todas las descripciones de las máquinas de Turing emparejadas con todos los posibles flujos de entrada en los que esas máquinas de Turing eventualmente se detendrán, no es recursivo. Por tanto, el problema de la detención se denomina no computable o indecidible .
Una extensión del problema de la detención se llama teorema de Rice , que establece que es indecidible (en general) si una lengua determinada posee alguna propiedad específica no trivial.
Sin embargo, el problema de la detención es fácil de resolver si permitimos que la máquina de Turing que decide hacerlo pueda funcionar para siempre cuando se le da una entrada que es una representación de una máquina de Turing que no se detiene. Por tanto, el lenguaje vacilante es recursivamente enumerable. Sin embargo, es posible construir lenguajes que ni siquiera sean recursivamente enumerables.
Un ejemplo sencillo de tal lenguaje es el complemento del lenguaje vacilante; ese es el lenguaje que consta de todas las máquinas de Turing emparejadas con cadenas de entrada donde las máquinas de Turing no se detienen en su entrada. Para ver que este lenguaje no es recursivamente enumerable, imaginemos que construimos una máquina de Turing M que es capaz de dar una respuesta definitiva para todas esas máquinas de Turing, pero que puede funcionar indefinidamente en cualquier máquina de Turing que finalmente se detenga. Luego podemos construir otra máquina de Turing que simule el funcionamiento de esta máquina, además de simular directamente la ejecución de la máquina dada en la entrada, intercalando la ejecución de los dos programas. Dado que la simulación directa eventualmente se detendrá si el programa que está simulando se detiene, y dado que, por supuesto, la simulación de M eventualmente se detendrá si el programa de entrada nunca se detendrá, sabemos que eventualmente una de sus versiones paralelas se detendrá. es, por tanto, un factor decisivo para el problema de la detención. Sin embargo, hemos demostrado anteriormente que el problema de la detención es indecidible. Tenemos una contradicción y, por tanto, hemos demostrado que nuestra suposición de que M existe es incorrecta. Por tanto, el complemento de la lengua vacilante no es recursivamente enumerable.
Se han desarrollado varios modelos computacionales basados en la concurrencia , incluida la máquina paralela de acceso aleatorio y la red de Petri . Estos modelos de computación concurrente todavía no implementan ninguna función matemática que las máquinas de Turing no puedan implementar.
La tesis de Church-Turing conjetura que no existe un modelo de informática eficaz que pueda calcular más funciones matemáticas que una máquina de Turing. Los informáticos han imaginado muchas variedades de hipercomputadoras , modelos de computación que van más allá de la computabilidad de Turing.
Imagine una máquina donde cada paso del cálculo requiere la mitad del tiempo del paso anterior (y, con suerte, la mitad de la energía del paso anterior...). Si normalizamos a 1/2 unidad de tiempo la cantidad de tiempo requerido para el primer paso (y a 1/2 unidad de energía la cantidad de energía requerida para el primer paso...), la ejecución requeriría
unidad de tiempo (y 1 unidad de energía...) para ejecutarse. Esta serie infinita converge a 1, lo que significa que esta máquina Zeno puede ejecutar un número contablemente infinito de pasos en 1 unidad de tiempo (usando 1 unidad de energía...). Esta máquina es capaz de decidir el problema de parada simulando directamente la ejecución de la máquina en cuestión. Por extensión, cualquier serie convergente infinita [debe ser demostrablemente infinita] funcionaría. Suponiendo que la serie infinita converge a un valor n , la máquina Zeno completaría una ejecución contablemente infinita en n unidades de tiempo.
Las llamadas máquinas Oracle tienen acceso a varios "oráculos" que ofrecen la solución a problemas específicos e indecidibles. Por ejemplo, la máquina de Turing puede tener un "oráculo de detención" que responde inmediatamente si una determinada máquina de Turing se detendrá alguna vez ante una determinada entrada. Estas máquinas son un tema central de estudio en la teoría de la recursividad .
Incluso estas máquinas, que aparentemente representan el límite de autómatas que podamos imaginar, tienen sus propias limitaciones. Si bien cada uno de ellos puede resolver el problema de la detención de una máquina de Turing, no pueden resolver su propia versión del problema de la detención. Por ejemplo, una máquina Oracle no puede responder a la pregunta de si una determinada máquina Oracle se detendrá alguna vez.
