máquina de turing universal

Hace no mucho leí en Microsiervos que un jóven de 20 años llamado Alex Smith había conseguido demostrar que la Máquina de Turing (2,3) es universal. Con esta demostración se bate el record a la menor Máquina de Turing Universal, obtenido por Stephen Wolfram, que encontró la demostración de que la máquina (2,5) es universal.

Gracias a esta proeza, el joven Alex se ha embolsado el nada despreciable premio de $25.000 ofrecido por WolframScience.

Alan Mathison Turing (1912-1954) fué un matemático y filósofo inglés. A lo largo de su corta vida, además de trabajar durante la Segunda Guerra Mundial como matemático dedicado a intentar descifrar los mensajes cifrados Nazis, en especial los que se obtenian mediante la máquina Enigma, introdujo muchos avances en la matemática moderna, que aún hoy en día perduran.

Introdujo en la aún joven rama de la inteligencia artificial un mecanismo conocido como Prueba de Turing para determinar si una máquina es inteligente. Según esta prueba, si un interlocutor humano que mantiene una conversación con una máquina es incapaz de determinar, sin tener información visual de esta, si se trata de una máquina o un humano, la máquina es entonces inteligente. Evidentemente, no existen aún máquinas capaces de pasar un test de estas características, pero este método ha servido para inspirar mecanismos de seguridad en internet como los Captchas.

Además de sus aportaciones más bien filosóficas a la rama de la Inteligencia Artificial, Turing dedicó muchos esfuerzos al desarrollo de la ciencia de la computación. Como respuesta a uno de los retos de Hilbert, desarrolló la Máquina de Turing. Esta máquina se define como un cabezal que se mueve sobre una cinta infinita dividida en casillas que contienen un símbolo determinado de una lista. Dicho cabezal únicamente puede: leer el símbolo de una casilla y su estado interno, modificar el contenido de la casilla y su estado interno y desplazarse una casilla hacia la izquierda o hacia la derecha.

La definición de una máquina de este tipo se hace mediante el número de símbolos posibles en la cinta, el número de estados de la máquina y la tabla que indica las acciones que realiza el cabezal para cada par símbolo/estado leído. Así, una máquina que tiene n posibles estados internos y puede manejar m símbolos se denota como una Máquina de Turing (n,m).

Turing indicó que se puede demostrar que es posible construir una Máquina de Turing capaz de emular a todas las demás máquinas posibles. A esta máquina la llamó Máquina Universal. Desde entonces, los matemáticos han intentado encontrar máquinas universales cada vez más pequeñas, es decir, con menos estados y símbolos.

El logro de Alex Smith ha sido, por lo tanto, demostrar que existe una Máquina de Turing de sólo 2 estados y 3 símbolos que es capaz de realizar las mismas tareas que cualquier máquina existente (computacionalmente hablando), incluido el ordenador con el que leéis esta noticia.

¿A que impresiona?