NeoFronteras

Demuestran que la máquina de Turing 2,3 es universal

Área: Matemáticas — jueves, 25 de octubre de 2007

Un estudiante de 20 años gana el premio de 25.000 dólares de un concurso convocado por Stephen Wolfram para quien demostrase la capacidad de cómputo universal de la máquina de Turing 2,3.

Foto
Una posible evolución de una máquina de Turing 2,3 se muestra de izquierda a derecha, estando la cinta representada verticalmente. Foto: wolframscience.

Usted, que está sentado delante de un ordenador o computadora, quizás no sea consciente de la teoría matemática que fue necesario desarrollar en las primeras décadas del siglo pasado para poder crear este tipo de máquinas.
Hubo muchos científicos (físicos y matemáticos principalmente) implicados en este campo. Uno de ellos fue Alan Turing, que en los años treinta desarrolló la máquina conceptual de cómputo que lleva su nombre. Pudo demostrar sobre el papel que se puede crear una máquina de Turing capaz de emular cualquier otra máquina de Turing.
Nuestros ordenadores y computadoras están basados en última instancia en este tipo modelos computacionales. Hay varios de ellos, como el cálculo lambda y otros, pero suelen ser equivalentes a la máquina de Turing y ésta es probablemente el modelo computacional más paradigmático y famoso.
La máquina de Turing es muy sencilla y se basa de una cinta sobre la que se escribe información mediante una cabeza lectora y grabadora que puede adoptar distintos estados. La cabeza lectora se basa en un conjunto de reglas fijas para moverse, leer y escribir caracteres sobre la cinta. El número de caracteres distintos que puede escribir o “colores” se fija al inicio, al igual que el número de estados que la cabeza lectora puede adoptar. Estos dos parámetros determinan la complejidad de la máquina, de este modo una máquina de Turing 10,8 puede adoptar 10 estados y usar 8 colores. Cuantos más estados y colores use más compleja será la máquina de Turing en cuestión.
En los años cincuenta y sesenta los científicos se plantearon cuál se sería la máquina de Turing más sencilla con capacidad de cómputo universal. Es decir, capaz de emular cualquier cálculo computable. A principio de los sesenta Marvin Minsky pudo demostrar que una máquina de Turing 7,4 tenía la capacidad de cómputo universal.
En los ochenta Stephen Wolfram, matemático famoso por crear el programa Mathematica, estudió los autómatas celulares, que en algunos casos eran equivalentes a máquinas de Turing, sospechando que muchos de ellos tenían la capacidad de cómputo universal. Lo demostró para el autómata con la regla 101 y encontró además que la Turing 2,5 era universal.
Una de las consecuencias que se podían extraer de estos resultados era que la computación universal era particularmente ubicua, que debía de darse en muchos sistemas y por tanto que se debía de encontrar en la naturaleza. Según Wolfram todo esto estaría conectado con cuestiones fundamentales en la ciencia, la naturaleza, la matemática y las ciencias de la computación. Además podría explicar cómo a partir de reglas muy sencillas surge la complejidad en los sistemas.
Más tarde demostró que la Turing 2,5 es universal y sospechó que la Turing 3,2 era demasiado simple para ser universal. Además, se sabe que las más sencillas, como la Turing 1,2, no son universales.
Para poder rellenar el hueco Wolfram lanzó un reto dotado con un premio de 25.000 dólares para aquel que fuera capaz de demostrar que la Turing 2,3 era universal.
Ahora el estudiante de electrónica y computación de 20 años Alex Smith de la Universidad de Birmingham (RU) ha ganado el premio al ser capaz de demostrar que, efectivamente, la máquina de Turing 2,3 es universal. Se ha basado en otro modelo computacional denominado sistema de etiquetas (tag system) que se sabe es universal, demostrando su equivalencia con la Turing 2,3. La demostración completa ocupa 44 páginas.
El resultado no es particularmente relevante en ciencias de la computación y a la mayoría de los expertos les trae sin cuidado por considerarlo pasado de moda, pero puede estimular nuevos trabajos en el área. Además nunca es tarde para un resultado teórico bonito.
Smith, por otro lado, dice no tener grandes proyectos para el dinero del premio, y de momento lo va simplemente a ingresarlo en el banco.

Fuentes y referencias:
Anuncio del premio.
Galería.
Demostración en pdf.
Introducción al problema.

Salvo que se exprese lo contrario esta obra está bajo una licencia Creative Commons.
Compartir »

5 Comentarios

  1. Martín :

    Desde luego es bonito saber que la máquina de Turing 2,3 es el sistema computacional más pequeño que, hasta el momento, se pueda concebir capaz de emular a cualquier otro sistema computacional, incluyendo el ordenador desde el cual escribo estas líneas.

  2. elzar:

    Si que es bonito Martín, estoy de acuerdo contigo. Espero que la comunidad científica siga dando noticias tan interesantes como ésta.
    Un saludo

  3. izamari:

    Creo que es muy complicada la explicación … a nosotros nos piden resúmenes de estos temas y no sabemos como explicarlos… por eso propongo que traten de no ponerle muchas explicaciones para que así nosotros los estudiantes los entendamos.
    Gracias.

  4. NeoFronteras:

    Lamentablemente incurre en una contradicción lógica. Normalmente las explicaciones ayudan a entender el tema, y no su supresión. Si logra entender algo es más fácil escribir sobre ello.
    Un resumen podría ayudar a copiarlo pero no a entenderlo. Además, recuerde que siempre se puede saber si algo se ha copiado literalmente. Basta poner una frase concreta en Google y automáticamente sale la fuente.
    Si no domina un tema lo ideal es que busque otro que pueda entender mejor. No haya nada como la satisfacción de haber comprendido un misterio de la Naturaleza, no lo deje escapar.

  5. Alberto:

    Es increíble que por contar intimidades en las televisiones o sacar fotos de famosos pagan cientos de millones de euros y por un avance científico solo 25.000 dólares que son 15.000 euros. Si el autor se liga a Paris Hilton le pagan cien veces más por una foto. ¡Qué vergüenza!

RSS feed for comments on this post.

Lo sentimos, esta noticia está ya cerrada a comentarios.