stringtranslate.com

Computabilidad

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 .

Problemas

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.

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 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:

Cálculo lambda
Un cálculo consta de 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 combinatoria
Un concepto que tiene muchas similitudes con el cálculo numérico, pero también existen diferencias importantes (por ejemplo, el combinador de punto fijo Y tiene forma normal en la lógica combinatoria, pero no en el cálculo numérico). La lógica combinatoria se desarrolló con grandes ambiciones: comprender la naturaleza de las paradojas, hacer que los fundamentos de las matemáticas sean más económicos (conceptualmente), eliminar la noción de variables (y, por lo tanto, aclarar su papel en las matemáticas).
Funciones μ-recursivas
Un cálculo consiste en 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. Por lo tanto, si en la secuencia definitoria de una función recursiva f ( x ) aparecen las funciones g ( x ) y h ( x , y ) , entonces pueden 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 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 arriba. El cálculo termina solo si el término final 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 la gramática para operar en cadenas de símbolos; también el sistema postcanónico .
Registrar máquina
Una idealización teórica de un ordenador. Hay varias variantes. En la mayoría de ellas, 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 de un almacén externo infinito (o de crecimiento dinámico) (visto en las máquinas de Turing) se puede entender reemplazando su papel 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, una secuencia o una matriz, etc.) por un número natural enorme 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.
Máquina de Turing
También similar a la máquina de estados finitos, excepto que la entrada se proporciona en una "cinta" de ejecución, de la que la máquina de Turing puede leer, escribir o mover hacia adelante y hacia atrás más allá de su "cabezal de lectura/escritura". Se permite que la cinta crezca hasta alcanzar un tamaño arbitrario. La máquina de Turing es capaz de realizar cálculos complejos que pueden tener una duración arbitraria. Este modelo es quizás el modelo de computación más importante en la ciencia informática, ya que simula la computación en ausencia de límites de recursos predefinidos.
Máquina de Turing multicinta
En este caso, 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 realizarse con una máquina de Turing normal, aunque esta última puede ser más lenta o requerir una región total más grande de su 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. Pero estas instrucciones son muy diferentes, por lo que, a diferencia de las máquinas de Turing, P′′ no necesita mantener un estado definido, porque toda la funcionalidad “similar a la de la memoria” solo puede proporcionarla 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, inspeccionando el símbolo en blanco. A pesar de su naturaleza minimalista, se ha convertido en el lenguaje formal parental de un lenguaje de programación implementado y (para entretenimiento) utilizado 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, 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:

Autómata finito determinista (DFA)
También llamada máquina de estados finitos. Todos los dispositivos informáticos reales que existen hoy en día pueden modelarse como una máquina de estados finitos, ya que todas las computadoras reales operan con recursos finitos. Una máquina de este tipo tiene un conjunto de estados y un conjunto de transiciones de estado que se ven afectadas por el flujo de entrada. Ciertos estados se definen como estados de aceptación. Se introduce un flujo de entrada en la máquina un carácter a la vez y las transiciones de estado para el estado actual se comparan con el flujo de entrada y, si hay una transición coincidente, la máquina puede ingresar a un nuevo estado. Si al final del flujo de entrada la máquina está en un estado de aceptación, entonces se acepta todo el flujo de entrada.
Autómata finito no determinista (NFA)
Otro modelo simple de computación, aunque su secuencia de procesamiento no está determinada de manera única. Puede interpretarse como que se toman múltiples caminos de computación simultáneamente a través de un número finito de estados. Sin embargo, es posible demostrar que cualquier NFA es reducible a un DFA equivalente.
Autómata de empuje hacia abajo
Similar a la máquina de estados finitos, excepto que tiene disponible una pila de ejecución, que puede crecer hasta alcanzar un tamaño arbitrario. Las transiciones de estado especifican además si se debe agregar un símbolo a la pila o si se debe eliminar un símbolo de la misma. Es más potente que un DFA debido a su pila de memoria infinita, aunque solo se puede acceder al elemento superior de la pila en cualquier momento.

El poder de los autómatas

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

El poder de las máquinas de estados finitos

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.

El poder de los autómatas pushdown

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.

El poder de las máquinas de Turing

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 parada

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:

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

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.

Más allá de los lenguajes recursivamente enumerables

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.

Modelos basados ​​en concurrencia

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.

Modelos de computación más fuertes

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.

Ejecución infinita

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.

Máquinas Oracle

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 .

Límites de la hipercomputació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.

Véase también

Referencias