Читать книгу Computación y programación funcional - Camilo Chacón Sartori - Страница 12

En 1936, Alan Turing formularía en su artículo «On Computable Numbers, with an Application to the Entscheidungsproblem» («Sobre los números computables, con una aplicación al problema de la decisión») la prueba de que no es posible dar respuesta al problema de decisión.

En este trabajo Turing presentaría lo que hoy en día llamamos máquina de Turing. Una abstracción matemática que representa la computación o, para ser más precisos, lo que es computable o no.

Michael Sipser, importante teórico de la computación diría en su libro Introduction to the Theory of Computation («Introducción a la teoría de la computación») lo siguiente:

Una máquina de Turing puede hacer todo lo que un ordenador de propósito general puede hacer. Sin embargo, hay algunos problemas que ni la máquina de Turing puede resolver. En concreto, estos problemas van más allá de los límites teóricos de la computación. (Sipser, 1997)

Esto quiere decir que, de hecho, una máquina de Turing puede hacer todo lo que un ordenador digital puede hacer (teóricamente) y que, a su vez, posee las mismas limitaciones. Por ello, queda claro que existe una influencia en su nivel más subyacente y esencial. Los ordenadores digitales que usamos en la actualidad corresponden a la arquitectura propuesta por John von Neumann en su borrador sobre EDVAC, en el que presenta la organización y el mecanismo de cómo debería funcionar este. Pero ya volveremos a esto.

Algunas características de una máquina de Turing son las que se presentan a continuación:

• Existe una cinta infinita (que puede entenderse como una memoria).

• Existe un cabezal que puede leer y escribir sobre cada celda de la cinta.

• El cabezal se puede mover de izquierda a derecha o viceversa.

• Existe una tabla de instrucciones; haciendo uso de ella, la máquina sabe qué valores puede reemplazar en cada operación y también cuándo detenerse.

Intuitivamente podría ser vista como se muestra en la figura 1.2:

Figura 1.2 Una representación visual de una máquina de Turing, donde el cabezal se posiciona en el símbolo 0. El símbolo al final (derecha) «#» significa que el procedimiento se va a parar (comúnmente conocido como halt, en inglés).

Ejemplo

Imaginemos que necesitamos realizar una operación muy simple: reemplazar cada aparición de cierto carácter en una secuencia de texto dada, por ejemplo, pasar de «00011010» a «11111111», o sea, reemplazar el carácter 0 por 1. Para ello, es necesario crear una máquina de Turing.

Para esto necesitamos una tabla de instrucciones que contenga la mecánica de cómo se realizará cada cambio de estado:

Tabla 1.1 Tabla de instrucciones de lo que debe realizar la máquina.

Considere el siguiente texto de entrada:

00011010#

La secuencia comenzaría de izquierda a derecha. Se agrega el símbolo «*» para indicar la posición del cabezal junto al carácter actual, que estará a la izquierda. Así pues, los cambios de estado serían los siguientes:

1. 0*0011010#

2. 10*011010#

3. 110*11010#

4. 1111*1010#

5. 11111*010#

6. 111111*10#

7. 1111111*0#

8. 11111111*#

9. 11111111#*

10. 11111111

En el primer paso, por ejemplo, el cabezal encuentra el carácter «0». Entonces, si vemos la tabla (primera fila), cuando el estado actual es E₀ y tiene el símbolo de entrada «0», se mantiene en el estado E₀ y lo cambia por el símbolo de salida «1», y el cabezal se mueve a la derecha. Esto ocurre sucesivamente hasta el tercer paso.

Ahora bien, si vamos al cuarto paso, que es donde encontramos un «1» en el cabezal, esto nos lleva a la segunda fila de la tabla. Si el estado actual es E₀ y el símbolo de entrada es «1», entonces se mantienen el estado actual y el valor «1», y se mueve el cabezal a la derecha.

El proceso sigue ocurriendo hasta que se encuentra el estado E₀ y el símbolo de entrada «#» (última fila de la tabla) devuelve un símbolo vacío «-» y detiene el procesamiento de la máquina de Turing (estado H). Por consiguiente, ya no hay ningún tipo de movimiento más por realizar. La computación se ha terminado.

Máquina de Turing universal

Una máquina de Turing universal U puede simular otra máquina de Turing T como una entrada. ¿Cómo lo logra? Leyendo (1) una descripción o tabla de instrucciones D_t de la máquina E_t a ser simulada y (2) los valores de entrada de dicha máquina E_t. Pues bien, con esto se puede, con una sola máquina, lograr «ejecutar» cualquier otra máquina de Turing.

Esto lo representamos con la figura 1.3, donde una máquina de Turing universal U puede simular otra máquina de Turing E_t con (1) descripción, (2) contenido y (3) estados. Esto conlleva la idea de que una máquina de Turing universal puede simular cualquier otra máquina de Turing dándole la información requerida en otra «cinta».

Figura 1.3 Una máquina de Turing universal.

Una máquina de Turing universal, concretamente, según dice Martin Davis, inspiró a John von Neumann para crear la primera arquitectura de computadoras en 1945, en su documento «First Draft of a Report on EDVAC» («Primer borrador de un informe sobre EDVAC»). En este documento, von Neumann presenta las ventajas del sistema binario sobre el decimal para las operaciones aritméticas elementales (+, -, ×, ÷), y según sus propias palabras, esto se explica por lo siguiente:

La principal virtud del sistema binario, en contraposición con el decimal, reside en la mayor simplicidad y velocidad con que se pueden ejecutar las operaciones elementales. (von Neumann, 1945)

Igualmente, se incorporan los registros especiales de memoria cuyo objetivo es, antes que nada, tener un conjunto de funciones ya definidas en memoria (por ejemplo: √, ||, log₁₀, log₂, ln, sin, etc.). Esto significa que no es necesario redefinir dichas funciones y, por ello, como es de suponer, el tiempo de cómputo se vería disminuido.

Por otro lado, el trabajo de Turing tuvo notables implicaciones en los fundamentos de la teoría de la complejidad computacional. Por su misma naturaleza, la capacidad explícita de secuencialidad de cada instrucción hace más simple poder clasificar problemas computacionales de acuerdo con su dificultad. Por ejemplo, las diversas clases de complejidad.

Antes de eso, primero debemos diferenciar dos cuestiones fundamentales: tiempo polinomial y tiempo exponencial. El tiempo polinomial, o mejor dicho, el tiempo polinomial de un algoritmo, es aquel en el que el tiempo de cómputo crece según la cantidad de datos de entrada n, los cuales no son exponenciales. Esto significa que la computación es más rápida. En la tabla 1.2 se presentan varios algoritmos⁴ clásicos, que usan la notación Big O⁵ (en el peor de los casos):

Tiempo polinomial	Tiempo exponencial
Búsqueda lineal	O(n)	Knapsack 0/1	O(2n)
Búsqueda binaria	O(log n)	Travelling salesman problem	O(2n)
Quicksort	O(n2)	Graph coloring	O(2n)
Merge sort	O(n log n)	Hamylton cycle	O(2n)

Tabla 1.2 Comparación de complejidad algorítmica entre tiempo polinomial y tiempo exponencial.

Cualquier algoritmo que tenga una complejidad elevada a la enésima potencia (como los que aparecen en la columna de la derecha) es computacionalmente demasiado complejo de solucionar en un tiempo de cómputo óptimo (polinomial). Esto se traduce en que se tarda demasiado tiempo en terminar la computación.

Pasemos a ver las principales clases de complejidad:

• P (polynomial en inglés). Es la clase de problema que es posible tratar, es decir, hay un algoritmo determinístico que lo resuelve de manera eficiente en un tiempo polinomial. Por ejemplo, los algoritmos de ordenamiento y de búsqueda de una subcadena dentro de un texto o del camino más corto entre dos nodos dentro de un grafo, entre otros.

• NP (non-deterministically polynomial en inglés). La clase de problemas que pueden ser resueltos en un tiempo polinomial por un algoritmo no determinístico. (Esto último significa que son algoritmos que tienen un componente de selección aleatorio en su comportamiento, es decir, cada ejecución con los mismos argumentos no asegura el mismo valor de devolución. Por ejemplo, el algoritmo de colonia de hormigas, algoritmos genéticos, etc.) Los problemas NP son problemas de decisión. De esta clase nace la siguiente pregunta: ¿estos problemas pueden resolverse de manera determinista en un tiempo polinomial? Es decir, ¿es P = NP? Esto no ha sido probado y es uno de los problemas del siglo que aún sigue abierto. Ejemplos de problemas de esta clase: la factorización de números enteros y el isomorfismo de grafos.

• NP-Completo. Problemas más difíciles que los NP y, obviamente, que los P. Son problemas de decisión que se diferencian de los NP en lo siguiente: representan el conjunto de todos los problemas X en NP que se pueden reducir a cualquier otro problema NP en tiempo polinomial, es decir, intuitivamente lo entendemos así: si tenemos la solución para el problema X, entonces podríamos encontrar rápidamente la solución al problema Z. Ejemplos de problemas de esta clase son: 3-SAT, el problema del vendedor viajero, camino hamiltoniano, etc.

• NP-Difícil (NP-hard en inglés). Son problemas de decisión tan complejos como los NP, pero no se sabe si existe un algoritmo verificable en tiempo polinomial para todos los casos. Esto último nunca ha sido demostrado, es decir, si P ≠ NP, entonces los problemas de esta categoría no pueden ser resueltos en tiempo polinomial. Un ejemplo de este tipo es el problema de la parada, que es NP-Difícil pero no NP-Completo.

La figura 1.4 resume la relación entre estas tres clases de complejidad:

Figura 1.4 Características de cada clase de problema de complejidad. El signo «|» significa «o».

Resumiendo, las clases de complejidad existen porque hay muchos tipos de problemas computacionales y una forma de tratarlos de mejor manera es clasificarlos por su dificultad. Con esto es posible diseñar técnicas algorítmicas más adecuadas según su clase.