Page 40 - 06 Turing

una máquina con dos o más cabezas de lectura/escritura que leen y
escriben sobre una misma cinta, lo que aumenta su eficiencia com-
putacional. Otra posibilidad es la máquina de Turing capaz de leer
datos en celdas de más de una cinta. También se han propuesto
otras alternativas, como, por ejemplo, la máquina de Turing no de-
terminista, una máquina en la que la tabla de acciones contiene más
de una regla de transición para un cierto estado, eligiéndose al azar
la regla de transición con la que se actualizará su estado. Sin em-
bargo, el diseño que representó un verdadero desafío es la clase de
máquina a la que Turing denominó oráculo o máquina-o. Con ella
intentó superar los límites de su máquina convencional, dotándola
de poder computacional suficiente como para resolver el proble-
ma de la parada o problemas cuya solución no fuera expresable por
medio de un alg01itmo. Una máquina-o es una máquina de Turing
que está conectada a una caja negra, denominada oráculo, que le
permite superar sus limitaciones. Si se prefiere, puede pensarse en
el oráculo como una segunda cinta en la máquina de Turing. Para
consultarla, esta utiliza un símbolo especial llamado marcador.
Entre dos marcadores se sitúa el símbolo sobre el que la máquina
quiere consultar al oráculo. Seguidamente, la máquina de Turing
pasa a un estado especial denominado estado llamada, enviando
así una petición al oráculo. Si este reconoce el símbolo como per-
teneciente a su conjunto de símbolos, entonces la máquina pasará
al estado-1 y, en caso contrario, es decir, si el oráculo no reconoce
el símbolo en cuestión, pasará al estado-O. La máquina-o fue un
primer intento realizado por Turing de lo que con posterioridad se
ha llamado hipercomputación, propuestas que van más allá de la
idea de computación introducida por el propio científico inglés.

EL PROBLEMA DE LA PARADA: ¿pQR QUÉ SE CUELGA
UN ORDENADOR?

Una vez ideada la máquina de Turing, el científico inglés estudiaría
un «problema de decisión» por medio de su propia invención, co-
nocido desde entonces como problema de la parada (halting pro-

40 lOUÉ ES UN ORDENADOR?