La computabilidad es la capacidad de resolver un problema de manera eficaz. Es un tema clave en el 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 vinculada a la existencia de un algoritmo para resolverlo.
Los modelos de computabilidad más estudiados son las funciones computables de Turing y las μ-recursivas , y el cálculo lambda , todos ellos con una potencia computacional equivalente. También se estudian otras formas de computabilidad: las nociones de computabilidad más débiles que las máquinas de Turing se estudian en la teoría de autómatas , mientras que las nociones de computabilidad más fuertes que las máquinas de Turing se estudian en el campo de la hipercomputación .
Una idea central en computabilidad es la de un problema ( computacional ) , que es una tarea cuya computabilidad puede ser explorada.
Hay dos tipos principales 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 que está destinada a realizar la tarea en cuestión. Los modelos generales de computación equivalentes a una máquina de Turing (ver la 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 de inserción no deterministas son otro formalismo equivalente a las gramáticas libres de contexto.
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 manera se obtiene la jerarquía de lenguajes de Chomsky .
Otros modelos restringidos de computación incluyen:
Con estos modelos computacionales en la mano, podemos determinar cuáles son sus límites, es decir, ¿qué clases de lenguajes pueden aceptar?
Los científicos informáticos denominan 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 finitos 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 un lenguaje de este tipo es el conjunto de todas las cadenas formadas por 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 existe una máquina de este tipo M. M debe tener un número de estados n . Ahora consideremos la cadena x formada por 'a' seguidas de 'b'.
Como M lee en x , debe haber algún estado en la máquina que se repita cuando lee en la primera serie de 'a', ya que hay 'a' y solo n estados por el principio del palomar . Llamemos a este estado S y, además, sea d el número de 'a' que nuestra máquina leyó para llegar desde la primera ocurrencia de S a alguna ocurrencia posterior durante la secuencia 'a'. Sabemos, entonces, que en esa segunda ocurrencia de S , podemos agregar un d (donde ) 'a' adicional 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', lo 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 igual número de 'a' y 'b' y una cadena con 'a' y 'b'.
Sabemos, por lo tanto, que este lenguaje no puede ser aceptado correctamente por ninguna máquina de estados finitos y, por lo tanto, no es un lenguaje regular. Una forma más general de este resultado se denomina lema de bombeo para lenguajes regulares , que se puede utilizar para demostrar que una máquina de estados finitos no puede reconocer clases amplias de lenguajes.
Los científicos informáticos definen un lenguaje que puede ser aceptado por un autómata de inserción como un lenguaje libre de contexto , que puede especificarse como una gramática libre de contexto . El lenguaje que consiste en cadenas con números iguales de 'a' y 'b', que demostramos que no era un lenguaje regular, puede ser decidido por un autómata de inserción. Además, en general, un autómata de inserción puede comportarse como una máquina de estados finitos, por lo que puede decidir cualquier lenguaje que sea regular. Este modelo de computación es, por lo tanto, estrictamente más poderoso que las máquinas de estados finitos.
Sin embargo, resulta que hay lenguajes que tampoco pueden ser decididos por un autómata de empuje. 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 dicho lenguaje es el conjunto de números primos.
Las máquinas de Turing pueden decidir cualquier lenguaje independiente del contexto, además de los lenguajes que no pueden decidirse mediante un autómata de tipo push-down, como el lenguaje compuesto por números primos. Por lo tanto, se trata de un modelo de computación estrictamente más potente.
Debido a que las máquinas de Turing tienen la capacidad de "retroceder" 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 computación descritos anteriormente. Es posible construir una máquina de Turing que nunca terminará de funcionar (se detendrá) en algunas entradas. Decimos que una máquina de Turing puede decidir un lenguaje si finalmente se detendrá en todas las entradas y dará una respuesta. Un lenguaje que puede decidirse de esta manera se llama lenguaje recursivo . Podemos describir además máquinas de Turing que eventualmente se detendrán y darán una respuesta para cualquier entrada en un lenguaje, pero que pueden funcionar indefinidamente para cadenas de entrada que no están en el lenguaje. Tales máquinas de Turing podrían decirnos que una cadena dada está en el lenguaje, pero nunca podemos estar seguros en función de su comportamiento de que una cadena dada no está en un lenguaje, ya que puede funcionar indefinidamente en tal caso. Un lenguaje que es aceptado por una máquina de Turing de este tipo se llama lenguaje recursivamente enumerable .
Resulta que la máquina de Turing es un modelo de autómata extremadamente potente. 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, añadir una cinta adicional a la máquina de Turing, dándole una superficie infinita bidimensional (o tridimensional o de cualquier dimensión) con la que trabajar, puede simularse con una máquina de Turing con la cinta unidimensional básica. Por lo tanto, estos modelos no son más potentes. De hecho, una consecuencia de la tesis de Church-Turing es que no hay 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 hay que hacerse entonces es: ¿existen lenguajes que sean recursivamente enumerables, pero no recursivos? Y, además, ¿existen lenguajes que ni siquiera sean recursivamente enumerables?
El problema de la detención es uno de los problemas más famosos en la ciencia informática, porque tiene profundas implicaciones en la teoría de la computabilidad y en la forma en que utilizamos las computadoras en la práctica diaria. El problema se puede formular de la siguiente manera:
En este caso, no se trata de una simple pregunta sobre un número primo o un palíndromo, sino que se da la vuelta a la situación y se le pide a una máquina de Turing que responda a una pregunta sobre otra máquina de Turing. Se puede demostrar (véase el artículo principal: Problema de la 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 dado 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 sepas si finalmente se detendrá. El lenguaje que consiste en todas las descripciones de máquinas de Turing emparejadas con todos los flujos de entrada posibles en los que esas máquinas de Turing finalmente se detendrán, no es recursivo. Por lo tanto, el problema de la detención se llama no computable o indecidible .
Una extensión del problema de detención se denomina teorema de Rice , que establece que es indecidible (en general) si un lenguaje dado posee alguna propiedad no trivial específica.
Sin embargo, el problema de la detención es fácil de resolver si permitimos que la máquina de Turing que la decide pueda funcionar indefinidamente si se le da una entrada que es una representación de una máquina de Turing que no se detiene. Por lo tanto, el lenguaje de la detención es recursivamente enumerable. Sin embargo, es posible construir lenguajes que ni siquiera sean recursivamente enumerables.
Un ejemplo sencillo de un lenguaje de este tipo es el complemento del lenguaje de parada; es decir, el lenguaje que consiste en 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 para siempre en cualquier máquina de Turing que finalmente se detenga. Podemos entonces construir otra máquina de Turing que simule el funcionamiento de esta máquina, junto con simular directamente también 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 finalmente se detendrá si el programa que está simulando se detiene, y dado que por suposición la simulación de M finalmente se detendrá si el programa de entrada nunca se detuviera, sabemos que finalmente hará que una de sus versiones paralelas se detenga. es, por tanto, un decisor para el problema de parada. Sin embargo, hemos demostrado previamente que el problema de parada es indecidible. Tenemos una contradicción y, por lo tanto, hemos demostrado que nuestra suposición de que M existe es incorrecta. Por lo tanto, el complemento del lenguaje de parada no es recursivamente enumerable.
Se han desarrollado varios modelos computacionales basados en la concurrencia , entre ellos la máquina de acceso aleatorio paralelo y la red de Petri . Estos modelos de computación concurrente aún no implementan ninguna función matemática que no pueda implementarse mediante máquinas de Turing.
La tesis de Church-Turing plantea que no existe un modelo eficaz de computación que pueda calcular más funciones matemáticas que una máquina de Turing. Los científicos informáticos han imaginado muchas variedades de hipercomputadoras , modelos de computación que van más allá de la computabilidad de Turing.
Imaginemos una máquina en la que 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 necesaria para el primer paso (y a 1/2 unidad de energía la cantidad de energía necesaria 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 infinito contable de pasos en 1 unidad de tiempo (usando 1 unidad de energía...). Esta máquina es capaz de resolver el problema de detención simulando directamente la ejecución de la máquina en cuestión. Por extensión, cualquier serie infinita convergente [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 infinita contable en n unidades de tiempo.
Las llamadas máquinas Oracle tienen acceso a varios "oráculos" que proporcionan la solución a problemas indecidibles específicos. 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 recursión .
Incluso estas máquinas, que aparentemente representan el límite de autómatas que podríamos imaginar, tienen sus propias limitaciones. Si bien cada una de ellas 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.
