reseña de computacion

ISSN 0717-9103
ISSN Online 0718-8307

Ingeniería Industrial-Año 10 Nº2: 49-63, 2011

COMPUTABILIDAD Y COMPUTACIÓN CUÁNTICA:
REVISIÓN DE MODELOS ALTERNATIVOS DE COMPUTACIÓN
COMPUTABILITY AND QUANTUM COMPUTING: A SURVEY OF
ALTERNATIVE FORMAL COMPUTING MODELS
Guillermo Morales-Luna1
1
Departamento de Computación Centro de Investigación y de Estudios Avanzados del
IPN(CINVESTAV) México,D. F., México.

RESUMEN
Este es el primer ensayo, de una serie de dos, en los que se quiere presentar visiones
panorámicas de la noción de computabilidad de dos nuevos paradigmas de computación. A
saber, la computación cuántica y la computación basada en ADN o molecular, así como de
los circuitos integrados tridimensionales que constituyen una alternativa para continuar con laminiaturización de procesadores hasta más allá del orden del nanómetro. Aquí se parte de la
misma noción de computación, de sus limitaciones lógicas y se delinea el problema de decidir
si acaso el determinismo y el no-determinismo coinciden en dispositivos de complejidades
polinomiales en el tiempo. En cuanto a la computación cuántica, se presenta a sus elementos
matemáticos básicos y a las ventajas queimplican en comunicaciones y criptografía.
Finalmente se menciona a algunas de las alternativas actuales para implementarlas. Esta
presentación es una reseña del estado actual del área, y tan sólo es novedosa en cuanto a
sus ejemplos; está escrita originalmente en lengua castellana, y está dirigida a un público
extenso, conformado tanto por profesionistas como estudiantes de nivel universitario.Palabras claves: Complejidad algorítmica, información, computación y criptografía
cuánticas.

ABSTRACT
This is the first essay, in a series of two, devoted to review the new paradigms of Computing,
namely quantum computing and molecular computing, as well as 3D integrated circuits aiming
to miniaturization processes beyond nanometers. An analysis of the computability basics and
its limitsis realized and the essential P=NP problem is sketched. Quantum computing is
introduced, and its implications in hard problems and in cryptography. Finally, some current
implementation strategies are outlined. This is just a survey article, its novelty is the presentation
suited to a wide audience.
Keywords: Algorithmic complexity, quantum information, computing and cryptography.

Autor paracorrespondencia: gmorales@cs.cinvestav.mx
Recibido: 22.12.2011 Aceptado: 12.03.2012

49

Ingeniería Industrial-Año 10 Nº2: 49-63, 2011

Universidad del Bío-Bío

ESTADO DEL ARTE
Computabilidad
La noción de computación es propia del siglo XX. En la década de los 30 surgió naturalmente
la pregunta de si acaso se podría construir máquinas que pudieran pensar, y en 1950 AlanTuring (Turing, 1950) planteó formalmente esta pregunta, desarrollando lo que se conocería
posteriormente como la prueba de Turing: Dos partes, una humana y la otra, que puede ser
un humano o una máquina, dialogan de manera libre, y la parte humana trata de determinar
si su contraparte es o no humana. Una máquina supera la prueba si el humano no puede
decidir que ésa es una máquina. En ese entonces, Turingasevera que para finales del siglo
XX habrá computadoras que prácticamente habrían de superar la prueba. Se es testigo de
que esta predicción se cumplió aproximadamente. Desde la década de los 90 se interactúa
cotidianamente con máquinas en lenguaje natural, y muchas veces no se repara en que el
interlocutor sea un autómata. Acaso se puede cuestionar todavía si la predicción de Turing secumplió, pues, por lo general, los interlocutores automáticos son recognoscibles. Un problema
de suma actualidad es una variante de la prueba de Turing: un autómata ha de reconocer que
su interlocutor sea un humano y no un robot (CMU, 2000) -para fines de registro de cuentas de
correo electrónico, por ejemplo.
Desde el final de la década de los 30 del siglo XX, las computadoras surgieron para...