Computabilidad

La computabilidad es la capacidad de resolver un problema mediante un procedimiento 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 ligada a la existencia de un algoritmo para resolverlo.

Los modelos de computabilidad más estudiados son las funciones Turing-computables y μ-recursivas , y el cálculo lambda , todos los cuales poseen 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 .

Problemas

Una idea central en la computabilidad es la de un problema ( computacional ) , que es una tarea cuya computabilidad puede explorarse.

Existen dos tipos principales de problemas:

Un problema de decisión define un conjunto S , que puede ser un conjunto de cadenas, números naturales u otros objetos tomados de un conjunto mayor U. Un ejemplo particular del problema consiste en decidir, dado un elemento u de U , si u pertenece a S. Por ejemplo, sea U el conjunto de los números naturales y S el conjunto de los números primos. El problema de decisión correspondiente corresponde a la prueba de primalidad .
Un problema de funciones consiste en una función f de un conjunto U a un conjunto V. Un ejemplo de este problema es calcular, dado un elemento u en U , el elemento correspondiente f ( u ) en V. Por ejemplo, U y V pueden ser el conjunto de todas las cadenas binarias finitas, y f puede tomar una cadena y devolver la cadena obtenida al invertir los dígitos de la entrada (por ejemplo, f(0101) = 1010).

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.

Modelos formales de computación

Un modelo de computación es una descripción formal de un tipo particular de proceso computacional. La descripción suele adoptar la forma de una máquina abstracta diseñada para realizar la tarea en cuestión. Algunos modelos generales de computación equivalentes a una máquina de Turing (véase la tesis de Church-Turing ) incluyen:

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 reducción beta .
Lógica combinatoria: Un concepto que tiene muchas similitudes con $\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 $\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 consta de una función μ-recursiva, es decir, su secuencia definitoria, cualquier valor de entrada y una secuencia de funciones recursivas que aparecen en la secuencia definitoria con entradas y salidas. Así, si en la secuencia definitoria de una función recursiva $f (x)$ aparecen las funciones $g (x)$ y $h (x, 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 derivarse de las entradas anteriores mediante composición , recursión primitiva o μ-recursión . Por ejemplo, si $f (x) = h (x, g (x))$ , entonces para que aparezca $f (5) = 3 , deben aparecer términos como$ $g (5) = 6$ y $h (5,6) = 3.$ El cálculo termina solo si el último término da el valor de la función recursiva aplicada a las entradas.
Sistemas de reescritura de cadenas: Incluye algoritmos de Markov , que utilizan reglas similares a las gramáticas para operar en cadenas de símbolos; también el sistema postcanónico .
Máquina registradora: Idealización teórica de una computadora. Existen 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 escasas), por ejemplo, solo existen la decrementación (combinada con un salto condicional) y el incremento (y la parada). La ausencia de una memoria externa infinita (o de crecimiento dinámico) (presente en las máquinas de Turing) se puede comprender 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 representar algo complejo (por ejemplo, una secuencia o una matriz, etc.) mediante un número natural suficientemente grande; la uniambigü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.
Máquina de Turing: Similar a una máquina de estados finitos, la entrada se proporciona en una "cinta" de ejecución, que la máquina de Turing puede leer, escribir o mover hacia adelante y hacia atrás frente a su "cabezal" de lectura/escritura. La cinta puede crecer hasta alcanzar un tamaño arbitrario. La máquina de Turing es capaz de realizar cálculos complejos de duración indefinida. Este modelo es quizás el más importante en informática, ya que simula la computación sin límites de recursos predefinidos.
Máquina de Turing multitapa: Aquí puede haber más de una cinta; además, puede haber varios cabezales por cinta. Sorprendentemente, cualquier cálculo que pueda realizar este tipo de máquina también puede ser realizado por una máquina de Turing convencional, aunque esta última puede ser más lenta o requerir una mayor superficie de cinta.
PAG'': Al igual que las máquinas de Turing, P′′ utiliza una cinta infinita de símbolos (sin acceso aleatorio) y un conjunto de instrucciones bastante minimalista. Sin embargo, estas instrucciones son muy diferentes; por lo tanto, a diferencia de las máquinas de Turing, P′′ no necesita mantener un estado distinto, ya que toda la funcionalidad de "memoria" puede ser proporcionada únicamente por la cinta. En lugar de reescribir el símbolo actual, puede realizar un incremento aritmético modular sobre él. P′′ también tiene un par de instrucciones para un ciclo, que inspeccionan el símbolo vacío. A pesar de su naturaleza minimalista, se ha convertido en el lenguaje formal de origen de un lenguaje de programación implementado y utilizado (con fines de entretenimiento) llamado Brainfuck .

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 son los autómatas finitos , que 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.

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 .

Otros modelos de computación restringidos incluyen:

Autómata finito determinista (AFD): También llamada máquina de estados finitos. Todos los dispositivos informáticos actuales pueden modelarse como máquinas de estados finitos, dado que todos los ordenadores reales operan con recursos finitos. Dicha máquina posee un conjunto de estados y un conjunto de transiciones de estado que dependen del flujo de entrada. Ciertos estados se definen como estados de aceptación. El flujo de entrada se introduce en la máquina carácter a carácter, y las transiciones de estado del estado actual se comparan con el flujo de entrada. Si existe una transición coincidente, la máquina puede pasar a un nuevo estado. Si al final del flujo de entrada la máquina se encuentra en un estado de aceptación, entonces se acepta todo el flujo de entrada.
Autómata finito no determinista (AFN): Otro modelo sencillo de computación, aunque su secuencia de procesamiento no está determinada de forma única. Puede interpretarse como la ejecución simultánea de múltiples rutas de computación a través de un número finito de estados. Sin embargo, es posible demostrar que cualquier autómata finito no determinista (AFND) es reducible a un autómata finito determinista (AFD) equivalente.
autómata de empuje: Similar a una máquina de estados finitos, con la diferencia de que dispone de una pila de ejecución que puede crecer hasta alcanzar un tamaño arbitrario. Las transiciones de estado especifican, además, si se añade o se elimina un símbolo de la pila. Es más potente que un autómata finito determinista (AFD) debido a su pila de memoria infinita, aunque solo se puede acceder al elemento superior de la pila en cada momento.

El poder de los autómatas

Con estos modelos computacionales, podemos determinar cuáles son sus límites. Es decir, ¿qué clases de lenguajes pueden aceptar?

Potencia de las máquinas de estados finitos

Los 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 dicho lenguaje 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 tal máquina M. M debe tener algún número de estados n . Ahora consideremos la cadena x que consta de $(n+1)$ 'a's seguido de $(n+1)$ 'b's.

A medida que M lee x , debe haber algún estado en la máquina que se repita a medida que lee en la primera serie de 'a', ya que hay $(n+1)$ 'a's y solo n estados por el principio del palomar . Llamemos a este estado S , y además sea d el número de 'a's 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 un d adicional (donde $d>0$ ) 'a's y volveremos al estado S. Esto significa que sabemos que una cadena de $(n+d+1)$ Las 'a's deben terminar en el mismo estado que la cadena de $(n+1)$ 'a's. Esto implica que si nuestra máquina acepta x , también debe aceptar la cadena de $(n+d+1)$ 'a's seguido de $(n+1)$ 'b's, que no está en el lenguaje de cadenas que contienen un número igual de 'a's y 'b's. En otras palabras, M no puede distinguir correctamente entre una cadena con un número igual de 'a's y 'b's y una cadena con $(n+d+1)$ 'a's y $n+1$ 'b's.

Sabemos, por lo tanto, que este lenguaje no puede ser aceptado correctamente por ninguna máquina de estados finitos y, en consecuencia, no es un lenguaje regular. Una forma más general de este resultado se conoce como el lema de bombeo para lenguajes regulares , que puede utilizarse para demostrar que amplias clases de lenguajes no pueden ser reconocidas por una máquina de estados finitos.

El poder de los autómatas de pila

Los informáticos definen un lenguaje que puede ser aceptado por un autómata de pila como un lenguaje libre de contexto , el cual puede especificarse como una gramática libre de contexto . El lenguaje que consiste en cadenas con igual número de 'a' y 'b', que demostramos que no es un lenguaje regular, puede ser determinado por un autómata de pila. Además, en general, un autómata de pila puede comportarse como una máquina de estados finitos, por lo que puede determinar cualquier lenguaje que sea regular. Este modelo de computación es, por lo tanto, estrictamente más potente que las máquinas de estados finitos.

Sin embargo, resulta que existen lenguajes que tampoco pueden ser determinados por un autómata de pila. 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 los números primos.

El poder de las máquinas de Turing

Las máquinas de Turing pueden decidir cualquier lenguaje libre de contexto (lenguaje aceptado por los autómatas de pila y las gramáticas libres de contexto), además de lenguajes que no pueden ser decididos por un autómata de pila, como el lenguaje de los 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, algo que no es posible con los otros modelos de computación descritos anteriormente. Es posible construir una máquina de Turing que nunca termine de funcionar (se detenga) con algunas entradas. Decimos que una máquina de Turing puede decidir un lenguaje si finalmente se detiene con todas las entradas y da una respuesta. Un lenguaje que puede decidirse de esta manera se llama lenguaje recursivo . Podemos describir además máquinas de Turing que finalmente se detienen y dan una respuesta para cualquier entrada de un lenguaje, pero que pueden funcionar indefinidamente para cadenas de entrada que no pertenecen al lenguaje. Dichas máquinas de Turing podrían decirnos que una cadena dada pertenece al lenguaje, pero es posible que nunca estemos seguros, basándonos en su comportamiento, de que una cadena dada no pertenece al lenguaje, ya que podría 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ómatas sumamente potente. Sorprendentemente, los intentos de modificar su definición para crear una máquina aún más potente han fracasado. Por ejemplo, añadir una cinta adicional a la máquina de Turing, dotándola de una superficie infinita bidimensional (o tridimensional, o de cualquier dimensión) con la que trabajar, puede simularse con una máquina de Turing que utilice 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 existe ningún modelo de computación razonable capaz de 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, ¿existen lenguajes que ni siquiera sean recursivamente enumerables?

El problema de la parada

El problema de la parada es uno de los problemas más famosos de la informática, ya que tiene profundas implicaciones en la teoría de la computabilidad y en cómo utilizamos las computadoras en la práctica cotidiana. El problema se puede formular de la siguiente manera:

Dada la descripción de una máquina de Turing y su entrada inicial, determine si el programa, al ejecutarse con dicha entrada, se detiene (completa) en algún momento. La alternativa es que se ejecute indefinidamente sin detenerse.

Aquí no planteamos una simple pregunta sobre un número primo o un palíndromo, sino que invertimos los papeles y le pedimos a una máquina de Turing que responda una pregunta sobre otra máquina de Turing. Se puede demostrar (véase el artículo principal: Problema de la parada ) 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 certeza si un programa dado se detendrá con una entrada determinada en todos los casos es simplemente ejecutarlo y comprobar si se detiene. Si se detiene, entonces sabemos que se detiene. Sin embargo, si no se detiene, es posible que nunca sepamos si eventualmente se detendrá. El lenguaje que consiste en todas las descripciones de máquinas de Turing junto con todas las posibles secuencias de entrada con las que esas máquinas de Turing se detendrán eventualmente, no es recursivo. Por lo tanto, el problema de la parada se denomina no computable o indecidible .

Una extensión del problema de la parada se denomina teorema de Rice , que establece que es indecidible (en general) si un lenguaje dado posee alguna propiedad no trivial específica.

Más allá de los lenguajes recursivamente enumerables

El problema de la parada es fácil de resolver si admitimos que la máquina de Turing que lo decide puede ejecutarse indefinidamente al recibir una entrada que representa una máquina de Turing que no se detiene. Por lo tanto, el lenguaje de parada es recursivamente enumerable. Sin embargo, es posible construir lenguajes que ni siquiera son recursivamente enumerables.

Un ejemplo sencillo de dicho lenguaje 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 con 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 ejecutarse indefinidamente en cualquier máquina de Turing que finalmente se detenga. Entonces podemos construir otra máquina de Turing. $M'$ que simula el funcionamiento de esta máquina, junto con la simulación directa de 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 detiene, sabemos que $M'$ Con el tiempo, una de sus versiones paralelas dejará de funcionar. $M'$ Por lo tanto, es un factor decisivo para el problema de la parada. Sin embargo, ya hemos demostrado que el problema de la parada es indecidible. Tenemos una contradicción, y así hemos demostrado que nuestra suposición de que M existe es incorrecta. Por consiguiente, el complemento del lenguaje de parada no es recursivamente enumerable.

Modelos basados en la concurrencia

Se han desarrollado varios modelos computacionales basados en la concurrencia , como la máquina de acceso aleatorio paralela y la red de Petri . Sin embargo, estos modelos de computación concurrente aún no implementan ninguna función matemática que no pueda ser implementada por máquinas de Turing.

Modelos de computación más robustos

La tesis de Church-Turing postula que no existe ningún modelo de computación eficaz capaz de realizar más funciones matemáticas que una máquina de Turing. Los informáticos han imaginado diversas variantes de hipercomputadoras , modelos de computación que superan la capacidad de computación de Turing.

Ejecución infinita

Imagina 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 requerida 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

1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots

unidad de tiempo (y 1 unidad de energía...) para ejecutar. Esta serie infinita converge a 1, lo que significa que esta máquina Zeno puede ejecutar un número infinito numerable 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 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 numerable en n unidades de tiempo.

Máquinas Oracle

Las llamadas máquinas oráculo tienen acceso a diversos "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 parada" que responde inmediatamente si una máquina de Turing determinada se detendrá alguna vez ante una entrada dada. Estas máquinas son un tema central de estudio en la teoría de la recursión .

Límites de la hipercomputación

Incluso estas máquinas, que aparentemente representan el límite de los autómatas que podríamos imaginar, se topan con sus propias limitaciones. Si bien cada una de ellas puede resolver el problema de la parada para una máquina de Turing, no pueden resolver su propia versión de dicho problema. Por ejemplo, una máquina oráculo no puede responder a la pregunta de si una máquina oráculo determinada se detendrá alguna vez.

Véase también

Referencias

Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 0-534-94728-X.Segunda parte: Teoría de la computabilidad, capítulos 3-6, págs. 123-222.
Christos Papadimitriou (1993). Complejidad computacional (1.ª ed.). Addison Wesley. ISBN 0-201-53082-1.Capítulo 3: Computabilidad, págs. 57–70.
S. Barry Cooper (2004). Teoría de la computabilidad (1.ª ed.). Chapman & Hall/CRC. ISBN 978-1-58488-237-4.