Decibilidad, Complejidad y Computabilidad: Fundamentos de la Teoría de la Computación con Máquinas de Turing

1. ¿En qué consiste la decibilidad de teorías lógicas?

Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, las reglas de inferencia y un esquema de derivación. A partir de los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría.

El conjunto de teoremas de la teoría forma un lenguaje formal.

Si es posible definir una máquina de Turing tal que reconozca el lenguaje de los teoremas, dicho lenguaje es decidible y la teoría también lo es. Dicho de otro modo, si el conjunto de teoremas visto como un lenguaje es reconocido por una máquina de Turing, entonces la TL es decidible. Y viceversa.

Puede hablarse entonces de manera indistinta de teorías lógicas o de lenguajes decidibles, pues allí donde existe una máquina de Turing capaz de reconocerlos, se establece la correspondencia entre la sintaxis de la teoría lógica (lenguaje formal) y el reconocimiento simbólico de la misma por parte de un autómata.

Desde el punto de vista semántico, las interpretaciones de las cadenas del lenguaje se realizan ya sea por el intérprete o bien por el compilador del lenguaje de programación en el cual se dan las instrucciones (ver sección de autómatas de pila). Las cadenas que resultan en instrucciones realizadas por la computadora pueden considerarse interpretadas como verdaderas y, por tanto, tienen, al menos, el modelo de la teoría lógica formada por tales cadenas.

2. ¿En teoría de la computación, a qué se refiere con el concepto de “decibilidad”?

Se dice que un sistema formal es decidible si existe un algoritmo que diga, en tiempo finito, si una cadena cualquiera es un teorema o no lo es.

El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas “generales” que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal.

Los lenguajes decidibles son conjuntos de palabras calculables mediante funciones recursivas, por lo cual también se los llama lenguajes recursivos.

3. ¿En qué consiste la teoría de la complejidad?

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante la aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante la aproximación a la cantidad de memoria utilizada para resolver un problema). Pueden estudiarse igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo.

La teoría de la complejidad difiere de la teoría de la computabilidad en que esta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Los problemas que tienen solución con orden de complejidad lineal son aquellos que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o costo computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Estos son problemas agrupados en la clase P.

Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son máquinas determinísticas), que en general poseen costos factoriales o combinatorios, pero que podrían ser procesados por una máquina no determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, la máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.

4. Explicar ampliamente en qué consiste la primera tesis de recursión

Todo operador entre funciones calculables que sea recursivo (esto es, que se defina la imagen de f mediante una función calculable en términos de la parte finita de f) tiene la función parcial computable que es el menor punto fijo; es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es la extensión de dicha función.

Esta tesis recibe su nombre porque podemos definir la función mediante la ecuación recursiva más general permitida por la recursividad primitiva, a saber:

f(x) = G(f, x)

donde G es un operador recursivo. La primera tesis de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador G. Así, y de acuerdo con la primera tesis de recursión, la clase de las funciones calculables está cerrada bajo la muy general forma de definición por recursión.

Como ejemplo interesante de aplicación de este tipo de recursión tenemos la función de Ackermann.

A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estrategia en el caso de la respuesta negativa es la siguiente: si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy simple: si tuviese solución efectiva, componiendo el algoritmo solución con el algoritmo de transformación obtendríamos una solución para el primer problema, efectivamente irresoluble. En sentido inverso, si se reduce un problema a otro cuya solución efectiva se conoce, entonces componiendo se obtiene la solución para el primer problema. Esta técnica es muy útil y se utiliza a menudo. Por otro lado, esta misma técnica es muy empleada en el campo de la complejidad algorítmica: para asegurar que un problema está en una clase de complejidad, basta reducirlo a otro de dicha clase, sin más, con la condición de que la reducción se realice en la correspondiente clase de complejidad.

5. ¿Qué son los lenguajes decidibles?

Los lenguajes decidibles son conjuntos de palabras calculables mediante funciones recursivas, por lo cual también se los llama lenguajes recursivos.

Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos a y b. Por ejemplo, la palabra vacía (es decir, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente a diferencia de lo que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.

Estos son algunos ejemplos de problemas de decisión expresados como lenguajes:

• Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
• Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
• Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que sea el camino más corto entre esos dos vértices.

6. ¿Cuál es el objetivo de la teoría de la computabilidad?

La teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o, equivalentemente, con una máquina de Turing. La teoría de la computabilidad se interesa por cuatro preguntas:

• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de Turing?
• ¿Qué problemas requieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?

La teoría de la complejidad computacional, por su parte, clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

El propósito inicial de la teoría de la computabilidad es precisar la noción intuitiva de función calculable; esto es, la función cuyos valores pueden ser calculados de forma automática o efectiva mediante un algoritmo. Así podemos obtener una comprensión más clara de esta idea intuitiva, y solo de esta forma podemos explorar matemáticamente el concepto de computabilidad y los conceptos relacionados con él, tales como decibilidad, etc. Surge así la teoría que producirá resultados positivos y negativos (estamos pensando en resultados de no computabilidad o de indecibilidad). La teoría de la computabilidad puede caracterizarse, desde el punto de vista de las ciencias de la computación, como la búsqueda de respuestas a las siguientes preguntas:

1. ¿Qué pueden calcular los ordenadores (sin restricciones de espacio, tiempo o dinero)?
2. ¿Cuáles son las limitaciones inherentes a los métodos automáticos de cálculo?

7. ¿De acuerdo a qué criterios estudia la teoría de la complejidad computacional?

8. ¿En qué difiere la teoría de la complejidad computacional respecto a la teoría de la computabilidad?

La teoría de la complejidad difiere de la teoría de la computabilidad en que esta última se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

9. Defina los lenguajes aceptables y decidibles

Lenguaje decidible: es aquel lenguaje L para el cual existe una máquina de Turing que puede aceptar cualquier cadena w ∈ L y rechazar cualquier cadena w ∉ L.

Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de Turing que pueda aceptar cualquier cadena w ∈ L y rechazar cualquier cadena w ∉ L.

Lenguaje aceptable

La máquina se detiene al reconocer la cadena del lenguaje.

Lenguaje decidible

La máquina dice si la cadena pertenece al lenguaje o no. Implica reconocer el complemento del lenguaje.

¡Existen lenguajes aceptables que no son decidibles! Un lenguaje es aceptable pero su complemento no.

10. ¿En qué consiste el problema de la parada (halting problem)?

El problema de la parada plantea la duda de si una máquina de Turing cualquiera con una cadena de entrada w (también cualquiera) se detiene o no. El problema está demostrado como irresoluble, por lo cual vale para aproximar otros problemas a este (halting problem) y demostrar por contradicción, como en esos otros problemas, que no se tiene solución.

El problema de la parada

• Máquina autoterminante: máquina con alfabeto {0, 1, ?} que se detiene cuando se le suministra como entrada la cadena que es su propia codificación.
• Existen máquinas de Turing para las que no es posible decidir si son autoterminantes o no; es decir, no puede saberse con certeza si se detendrán ante la cadena de entrada.

En definitiva, el problema de la parada no es decidible.