Una maquina de Turing es un modelo matemático que formaliza una definición de algoritmo, en cierta forma es básica un dispositivo que a partir de una entrada puede decidir una salida despues de ciertos pasos. Son fundamentales para la teoría matemática de la computación pues permite conocer lo que puede y no hacer una computadora.
Se admite que la maquina de Turing (MT) no es el único modelo estudiado por los especialistas, existen otros mas antiguos como los autómatas de pila, que son superados por la MT, que sin embargo ayudan a teorizar sobre algo, también están las Maquinas oráculo (en realidad, todavía no existen) sin embargo es un estudio muy interesante sobre maquinas que podrían resolver problemas NP-C en tiempos O(p(n)). Por ahora nos centramos en las MT.
Tenemos las MT deterministas, el modelo que conocemos comunmente y las MT no deterministas (nMT) que son maquinas que en alguna instancia del algoritmo pueden autoreplicarse y seguir rutas distintas (suena a recursividad, ¿no?) esto lo logra a través de su función de transición donde se puede Sobre-especificar mas de un comportamiento.
Se comprueba que para toda nMT existe una MT equivalente (Es decir que resuelve el mismo problema), sin embargo, la distinción entre una y otra es el tiempo que se tarda en resolver ese problema.
Pensemos en lo siguiente una nMT y su respectiva MT equivalente trabajando pro resolver un problema, es muy probable que la nMT termine primero que la otra, bastaría que una de las "auto-copias" de nMT encuentre la respuesta primero.
Ahora una computadora cuántica se comporta (procesamiento en universos paralelos o estados superpuestos) como una nMT, con esto tenemos un aumento considerable en la velocidad de resolución de problemas, pero no nos permite hacer nada nuevo, pues existen MT que resuelven esos mismos problemas en un tiempo mas largo.
Entonces, la computación cuántica nos permite reducir el margen de problemas antes considerados intratables y la posible ruptura de las claves criptograficas actuales, sin embargo esta lejos de alcanzar la hipercomputacion.
Por cierto la Computadora Cuántica anunciada por la empresa D-Wave resulto ser solo una acelerador de cálculos (cuántico, eso si) conectado a una CPU convencional.
Se admite que la maquina de Turing (MT) no es el único modelo estudiado por los especialistas, existen otros mas antiguos como los autómatas de pila, que son superados por la MT, que sin embargo ayudan a teorizar sobre algo, también están las Maquinas oráculo (en realidad, todavía no existen) sin embargo es un estudio muy interesante sobre maquinas que podrían resolver problemas NP-C en tiempos O(p(n)). Por ahora nos centramos en las MT.
Tenemos las MT deterministas, el modelo que conocemos comunmente y las MT no deterministas (nMT) que son maquinas que en alguna instancia del algoritmo pueden autoreplicarse y seguir rutas distintas (suena a recursividad, ¿no?) esto lo logra a través de su función de transición donde se puede Sobre-especificar mas de un comportamiento.
Se comprueba que para toda nMT existe una MT equivalente (Es decir que resuelve el mismo problema), sin embargo, la distinción entre una y otra es el tiempo que se tarda en resolver ese problema.
Pensemos en lo siguiente una nMT y su respectiva MT equivalente trabajando pro resolver un problema, es muy probable que la nMT termine primero que la otra, bastaría que una de las "auto-copias" de nMT encuentre la respuesta primero.
Ahora una computadora cuántica se comporta (procesamiento en universos paralelos o estados superpuestos) como una nMT, con esto tenemos un aumento considerable en la velocidad de resolución de problemas, pero no nos permite hacer nada nuevo, pues existen MT que resuelven esos mismos problemas en un tiempo mas largo.
Entonces, la computación cuántica nos permite reducir el margen de problemas antes considerados intratables y la posible ruptura de las claves criptograficas actuales, sin embargo esta lejos de alcanzar la hipercomputacion.
Por cierto la Computadora Cuántica anunciada por la empresa D-Wave resulto ser solo una acelerador de cálculos (cuántico, eso si) conectado a una CPU convencional.
1 comentario:
En realidad, las computadoras cuanticas existen desde el año de 1961, realizadas originalmente por IBM, y podían mantener hasta once estados (algo así como diez veces más que las computadoras binarias que actualmente utilizamos).
El detalle es que comercialmente hablando, los procesadores y equipos electrónicos para soportar los PC tal como los conocemos antes de los procesadores duales, son mucho más económicos que los computadores basados en los equipos cuanticos.
Un sitio interesante a visitar es:
http://computacioncuantica.blogspot.com/ donde hacen un interesante analísis de la noticia públicada por D-Wave, y los errores de afirmar algo, sin suficientes bases de conocimiento.
Saludos,
Publicar un comentario