La tesis de Church-Turing/Otras Máquinas

En este apartado se va a proceder a describir una serie de máquinas que

• o bien surgieron como intento de ampliar el poder computacional de la Máquina de Turing clásica
• o bien surgieron como pasatiempo y luego se demostraron computacionalmente equivalentes a la Máquina de Turing

Máquinas Cuánticas

En 1985, Deutsch presentó eldiseño de la primera Máquina Cuántica basada en una máquina de Turing. Para poder hacer esto, Deutsch enunció la tesis de Church de manera diferente dando lugar al denominado "Principio de Church-Turing-Deutsch".

A partir de este momento, diseña la primera máquina cuántica de Turing, cuya estructura es muy similar a la de una máquina de Turing clásica. Podemos definir una máquina cuántica, como una máquina formada por una serie de estados finitos, en la que destacan tres componentes:

• Una unidad de memoria finita
• Un procesador finito
• Un cursor

La siguiente ilustración muestra el esquema de una máquina cuántica:

Los QuBits (tal como se muestran en la ilustración anterior) nos permiten representar, que en esta máquina, el procesador está formado por un número finito de estados.

El juego de instrucciones de esta máquina, está formado por los cambios que se realizan sobre los QuBits de control (hay que tener en cuenta, que a veces esto puede depender del QuBit que se esté procesando en un momento dado sobre la cinta). Además, esta máquina sólo puede realizar una instrucción por unidad de tiempo.

La unidad de memoria es similar a la cinta de memoria de una máquina de Turing tradicional. La única diferencia entre ambas radica en el hecho de que, por cada elemento de la cinta de la máquina cuántica, tenemos un QuBit. Por tanto, podemos decir que el alfabeto de esta nueva máquina está formado por el espacio C2 del QuBit.

Finalmente, podemos definir el cursor como el elemento que nos permite comunicar la unidad de memoria y el procesador. Para almacenar su posición dentro de la cinta utilizamos una variable entera. Es necesario resaltar, que el cursor sólo puede procesar un elemento de la cinta por unidad de tiempo.

Máquinas con Oráculo (O-Machines ó MTO's)

En primer lugar vamos a proporcionar una definición de la palabra "oráculo". Tanto en la teoría de la complejidad como en la de la computabilidad, se define la palabra oráculo como una especie de "caja negra", cuya principal característica es que nos permite computar una función concreta de una sola vez.

De esta forma, seríamos capaces de encontrar una función que pudiera solucionar un problema NP-completo como, por ejemplo, el de la suma de un subconjunto. Incluso, podríamos descubrir que nos encontramos ante una función no computable (es decir, no recurrente) como, por ejemplo, el problema de la parada.

Las máquinas de Turing con oráculo nos permiten resolver, utilizando para ello información adicional, diferentes tipos de problemas.

Realmente, este tipo de máquinas representan un intento de Turing por añadirle mayor poder computacional a su máquina original (la Máquina de Turing), puesto que las Máquinas con Oráculo nos permiten resolver problemas que carecen de solución algorítmica.

En esencia, la MTO es una máquina de Turing, conectada a un oráculo, cuya principal característica es que está capacitada para determinar si un elemento pertenece o no a un conjunto específico de números naturales.

Esta máquina posee tres estados especiales:

• Estado llamada
• Estado-1
• Estado-0

Además, está formada por un elemento adicional, un símbolo especial que actúa de marcador: μ. Para poder usar su oráculo la máquina debe escribir, en dos recuadros de la cinta el marcador y, entre ambos el símbolo que se desea verificar. Una vez hecho esto, se pasará al estado de estado llamada. A partir de este momento,

1. Se envía una petición al oráculo.
2. La máquina finaliza en el estado-1 si el número escrito pertenece al conjunto oráculo y, en caso contrario, finaliza en el estado-0.

La siguiente ilustración muestra el funcionamiento del oráculo de una O-Machine:

Archivo:Simulacion funcionamiento maquina oraculo.png

A partir de los conceptos introducidos anteriormente, intuitivamente podemos afirmar que una MTO puede resolver el problema de la parada. Para ello, basta con facilitarle el alfabeto correspondiente a dicho problema. Este tipo de máquinas nos permite descubrir si para una determinada entrada n, la máquina se va a detener o no:

• Si no se detiene entonces la salida de la Máquina con Oráculo debe ser cero.
• Si se detiene retornará el resultado pertinente.

El problema de la parada se suele utilizar en la teoría de la recursión, puesto que nos permite describir los diferentes niveles de computabilidad existentes. De esta manera si podemos computar un conjunto en una MTO con un determinado oráculo, que denotaremos por la letra H, entonces podemos decir que es computable en H o recursiva en H.

Podemos considerar una máquina de Turing como un caso particular de una O-Machine. Para ello basta con imaginar una máquina de Turing con un oráculo vacío. Por tanto, este tipo de máquinas incrementan, de manera obvia, el poder computacional de una máquina de Turing clásica. Además, las MTO’s permiten computar todas las funciones recursivamente enumerables.

Una de las principales características de las Máquinas con Oráculo es que son capaces de computar una determinada función definida en el dominio de los números naturales. Sin embargo, no es posible encontrar una MTO que pueda procesar todas las funciones definidas en el dominio de los números naturales.

Esta paradoja se debe a que una Máquina Oráculo está formada por una Máquina de Turing clásica (es decir, una máquina de Turing formada por una serie tanto de transiciones finitas como de estados) y un oráculo (es decir, un conjunto, posiblemente, infinito de números). Esto nos permite trivializar la computación que ha sido generalizada, es decir, si pudiéramos elegir el oráculo en función de la definición de la función, entonces podríamos usar el oráculo para realizar búsquedas infinitas de símbolos.

A pesar de esta limitación, la noción de O-Machine resulta interesante y presenta unos fundamentos sólidos, puesto que nos permite resolver funciones utilizando para ello un oráculo determinado.

Máquinas de Turing Probabilísticas (MTP)

Las máquinas de Turing probabilísticas se utilizan, en la teoría de la complejidad computacional, principalmente para detallar las diferentes clases de complejidad existentes.

Se trata de máquinas no deterministas que toman decisiones basándose también en el azar. De manera informal, podemos definir una Máquina de Turing Probabilística (MTP) como una máquina en el que las decisiones se toman en base a una determinada probabilidad. Por simplicidad, podemos asumir que en, cada paso, la máquina tiene únicamente dos estados a los cuales se les asocia una probabilidad de ½. Este hecho, implica que al computar un problema de tamaño k obtenemos una probabilidad de 2-k (Herken, 1994).

Es decir, cada transacción tiene asociada la misma probabilidad, tal como se muestra en la siguiente figura:

Archivo:Maquinas probabilisticas.png

Podemos observar como cada posible estado tiene asociado una probabilidad. Además, la suma de estas probabilidades siempre debe sumar uno.

Cabe destacar que las MTP’s nos permiten resolver rápidamente problemas que en una máquina de Turing tradicional tardarían mucho tiempo en resolverse. Sin embargo, debemos resaltar que una MTP no aumenta el tamaño de las clases de las funciones que se pueden computar.

Asimismo, una MTP puede simular el funcionamiento de una Máquina de Turing para lo cual tendrá que simular, uno a uno, todos los posibles caminos correspondientes a los diferentes valores que se pueden obtener (Giuliano Benenti, 2004; Gill, 1974).

Leew, Moore, Shannon y Shapirio propusieron el primer modelo de MTP en 1955; en seguida, empezaron a surgir otros trabajos como el de Rabin en 1963 o el de Gill en 1974.

También podemos definir las Máquinas de Turing Probabilísticas como máquinas deterministas. Para ello deberemos añadir la instrucción write, de tal forma que el valor de la escritura quede distribuido, de manera uniforme, en el alfabeto que reconoce la máquina.

Como consecuencia de este hecho, una MTP puede proporcionarnos un resultado estocástico, es decir, dado un programa para la máquina, al que le asociamos una determinada entrada, puede ocurrir que el programa se ejecute en diferentes tiempos o, incluso, que no llegue a parar; y aunque parezca increíble, puede que durante una ejecución acepte una determinada entrada y no la admita durante la siguiente.

Por tanto, podemos concluir que podemos definir de diferentes formas la entrada a una MTP. Las clases de complejidad que incluyen RP, Co-RP, BPP y ZPP hacen referencia a dichas formas. Además, como es necesario restringir la máquina a usar tiempo logarítmico (en vez de polinómico que es lo habitual), es necesario definir una serie de clases análogas llamadas RL, Co-RL, BPL y ZPL. Si incluimos ambas restricciones obtendremos las clases RLP, Co-RLP, BPLP y ZPLP.

Es importante destacar que el modelo de cálculo que utilizan los computadores cuánticos es substancialmente probabilístico.

Esta es una forma de definir una MTP. Sin embargo, otros autores proponen otras definiciones.

Por ejemplo, Song Yan (Yan, 2002) define una MTP como una MT no determinista que contiene una serie de estados especiales llamados “coin-tossing states”. Para cada uno de estos estados se determinan dos estados posibles. Sin embargo, este concepto no resulta muy diferente de la definición que hemos utilizado anteriormente.

Giuliano Beneti define una máquina similar a la que utiliza Yan donde cada posibilidad tiene asociada una probabilidad de ½, de tal forma que cada estado tiene una probabilidad P de ser elegido y 1-P de no ser escogido. Esta máquina resulta difícil de simular.

Ja Mika Hirvensalo (Hirvensalo, 2004) y Colin P. Williams (Williams y Clearwater 1999), consideran una version más genérica de la MTP donde a partir de cada uno de los estados por los que pasa la máquina podemos obtener una serie de estados a los que nos podemos desplazar cuya suma de las probabilidades asociadas es uno. Una vez más, esta concepción de MTP no es muy diferente de la que hemos comentado originalmente.

El juego de la vida

Otro sistema del mismo poder de computación que la máquina de Turing es el juego de la vida.

En 1970, Conway publicó un pasatiempo que se ha hecho famoso. El juego de la vida es un juego donde no existen jugadores. Está formado por una malla bidimensional donde se coloca la información: los bits. Originalmente, se trataban de células que podían estar vivas (1) o muertas (0), ya que en un principio tan sólo era un juego.

Archivo:Juego vida1.png

Se realizan una serie de transiciones en el que las células pasan de un estado a otro. Las acciones que pueden darse en la malla son:

En una celda vacía puede:

• Aparecer una nueva => nace una célula
• Siga la celda vacía => no ocurre nada

En una celda ocupada:

• Desaparece la célula => muere
• Permance => sobrevive

El funcionamiento de este juego tiene tres puntos claves:

• un estado inicial (la colocación de las células al comienzo)
• unas reglas, que ahora veremos
• un estado final (si para)

En esta máquina las reglas que dominan los nacimientos y muertes no están determinados por un 'programa' externo ni por un algoritmo que se guarde independientemente de los datos. El comportamiento está implícito en la colocación de las células:

• Una célula nace si tiene 'exactamente' tres vecinas
• Una céluda muere si tiene menos de dos vecinas (de 'soledad')
• Una céluda muere si tiene más de tres vecinas (de 'superpoblación')

Que se puede codificar como 23/3 (Vecinas para sobrevivir/Vecinas para nacer). Existen variantes posteriores que modifican estos parámetros con la intención de que la máquina simule o no determinados comportamientos. Existe un conjunto de parámetros, por ejemplo, que hace que la máquina pueda contener patrones que se replican.

Pero volvamos a lo importante. Es una máquina teórica con el poder de computación de la máquina de Turing. A pesar de ello, no debemos expresar el problema como un autómata finito. Debemos expresarlo como una 'población inicial'. No se sabe si esto se acerca más o no al pensamiento humano o si podría considerarse un avance en la inteligencia artificial, pues lo único medianamente claro es la asunción de que la Tesis de Church-Turing sea cierta. Hasta que no se demostrara formalmente tal extremo (y parece complicado) será difícil establecer cuál es el mecanismo exacto para trasladar un pensamiento sobre una resolución (un algorítmo en un procesador especial: la mente) a su homólogo en una máquina teórica.

No debería ni tiene a priori que entenderse que este proceso sea más fácil de llevar a cabo sobre una Máquina de Turing, una máquina URM, o un juego de la vida. Arquitecturas de computadores (como la máquina de Von Neumann) en las que se apoyan paradigmas de muy alto nivel son abstracciones a la especificación formal de algoritmos cuya facilidad de uso no se ha comparado nunca con la que tuvieran posibles arquitecturas y paradigmas sobre el juego de la vida.

El mero hecho de que la capacidad intelectual humana esté materialmente presente en el funcionamiento de millones de neuronas de funcionamiento similar pero independiente y paralelo puede hacer pensar que esta aproximación sea más natural. De hecho, el mismo nombre tiene la palabra «vida», en alusión al espectáculo de ver evolucionar el juego, en el que parece verse una población evolucionar.

Entonces: la tesis de Church-Turing acercaría la equivalencia entre el poder computacional de esta máquina de la vida (el mismo que el de una MT) y el poder computacional humano. La propia concepción del juego asemejaría el funcionamiento de la máquina al del cerebro humano a primera vista más que la Máquina de Turing. ¿No estaremos perdiendo la oportunidad de atacar muchos problemas por otras vías?

Esperando que los avances por ese sentido llegaran, tendríamos que conformarnos con lo que actualmente aporta el juego de la vida. El estado inicial es el 'programa' que queremos que el juego de la vida ejecute. Se pueden construir patrones sobre esta malla: existen numerosos y documentados que generan sucesiones de números primos, puertas lógicas, sumadores, contadores,...

Como siempre, lo más divertido son los bucles infinitos, los patrones que no dejan de crecer o no se estabilizan. Probablemente lo más interesante, es si la concepción de que los datos evolucionan según su disposición y unas reglas simples en vez de según únicamente reglas complicadas puede ser útil para:

• estudios sociológicos
• estudios económicos
• cambios en el paradigma de programación
• replanteamiento de problemas hasta ahora sin solución conocida...
• o para muchos, un simple entretenimiento

Este applet en java permite ver una simulación del juego.