Link del día: El castor ocupado
Para quién no lo sabe, una Máquina de Turing es una máquina conceptual que consta de una “cabeza” sobre una “cinta” que puede moverse a izquierda o derecha, y leer o escribir. Se supone que con esas cuatro operaciones básicas, la máquina conceptual de Turing es capaz de realizar cualquier algoritmo computable existente. Sí, desde sumar dos números hasta calcular los dígitos de π. Desde revertir una cadena de texto hasta ser un servidor web (aunque lo veo como poco eficiente para eso). Para diagramar los algoritmos que ejecutan, se utilizan estados sobre los pasos que están ejecutando, y lo que se puede leer o escribir trata de un alfabeto en particular (es decir, algún conjunto de símbolos que se le llama alfabeto de esa máquina).
Lejos de ser una metáfora a la publicidades de pasta dental, el Castor Ocupado es un algoritmo para máquinas de Turing que, dada una cantidad de estados y una cantidad de elementos de alfabeto, debe correr tanto tiempo como sea posible para luego detenerse. ¿Qué significa esto en términos de computabilidad? Significa que debe de ser, bajo una cantidad limitada de condiciones, el algoritmo más largo no-infinito, lo cual, de alguna forma es un desafío para encontrar aquello que tome más tiempo de computación y no sea interminable.
¿La razón? No es pura búsqueda por el buscar como muchos pueden suponer (y como muchos lo buscan, por simple diversión), sino que detrás de esto existe la teoría de la computación, en cuanto a qué algoritmos son computables (por ejemplo, parece que los que se encuentran sí, pero el algoritmo para encontrarlos no), qué orden de computación tienen, y seguramente también se relaciona con el tipo de problemas que son computables y no computables, pero dejaré eso para el futuro.
Hubo alguien más, Peteris Krumins, que le encontró una veta artística. Por un lado, hay un video en Youtube de una máquina de Turing (construida) corriendo el castor ocupado, y por otro lado, Peteris mismo hizo un programita que va dejando un archivo con el estado de la cinta a medida que la máquina va ejecutando, y de ahí, generar una imagen en donde se vea gráficamente. En su blog, en el artículo del Problema del Castor Ocupado, habla de los algoritmos y los resultados que obtuvo ejecutándolos. Curiosas las imágenes, e impresionante la imagen de 5 estados y2 símbolos, para verla completa hace falta una bueeeeeeeena pantalla.
Soy un zorrinito ocupado.