Diferencia entre revisiones de «La tesis de Church-Turing/Otras Máquinas»
Contenido eliminado Contenido añadido
MÁQUINA DE ESCRIBIR… |
m Revertidos los cambios de 190.124.155.68 (disc.) a la última edición de 155.54.224.146 |
||
Línea 3:
* 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:
[[Imagen:maquina_cuantica.png]]
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) ==
| |||