Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»

 

== Máquinas Cuánticas ==

Una vez hecho esto, pasa a describir la máquina de Turing cuántica, muy parecida al modelo clásico de máquina de Turing. Podemos describir una máquina de Turing cuántica como una máquina de estados finitos que tiene tres componentes:

 

 

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

 

(( Falta la imagen ))

 

 

La unidad de memoria es muy parecida a la cinta de memoria que forma parte de la máquina de Turing clásica, pero se diferencia de ésta en que se tiene un QuBit en cada elemento de la cinta. Por tanto, podemos decir que el alfabeto de esta nueva máquina está formado por el espacio C2 del QuBit.

 

 

 

 

En primer lugar es necesario decir que tanto en la teoría de la complejidad como en la de la computabilidad, el término oráculo se define como una ''caja negra'' que nos permite computar una función en un sólo paso. Por tanto, podríamos encontrarnos con una función que es capaz de solucionar un problema NP-completo como, por ejemplo, el de la suma de un subconjunto. Incluso podría tratarse de una función no computable (es decir, no recurrente) como, por ejemplo, el problema de la parada.

La MTO es una máquina de Turing conectada a un oráculo que es capaz de determinar si un elemento pertenece a un conjunto específico de números naturales. Asimismo, esta máquina presenta tres estados especiales:

 

 

Además, la Máquina con Oráculo 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,

 

 

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

 

((Falta subir el dibujo))

 

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:

 

 

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.

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.

 

 

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

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.

 

 

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.