Carnaval de Matemáticas: La función castor afanoso cumple 60 años

Por Francisco R. Villatoro, el 14 mayo, 2022. Categoría(s): Ciencia • Colaboración externa • Informática • Matemáticas • Mathematics ✎ 2

Dicen que el test de Turing para saber si alguien es informático es pedirle que escriba una máquina de Turing que sume dos números representados por palotes (símbolo |). Se llama castor afanoso (busy beaver) a la máquina de Turing que escribe el máximo número de palotes antes de parar a partir de una cinta vacía usando solo n estados; la función castor afanoso BB(n) es dicho número máximo de palotes. El artículo de Tibor Radó que introdujo esta función se publicó en mayo de 1962 (hace 60 años) en The Bell System Technical Journal; aunque fue popularizada por A. K. Dewdney en 1984 en Scientific American.

Se sabe que BB(1) = 1, BB(2) = 6, BB(3) = 21, BB(4) = 107, pero se ignora el valor de BB(n) con n ≥5;  parece increíble que se ignore algo en apariencia tan sencillo, pero, por ejemplo, solo se sabe que BB(5) ≥ 47 176 870 (valor obtenido por Marxen y Buntrock en 1990). Si interesa conocer la historia de los avances en las funciones castor afanoso te recomiendo leer a Pascal Michel, «The Busy Beaver Competition: a historical survey,» arXiv:0906.3749 [math.LO] (19 Jun 2009), doi: https://doi.org/10.48550/arXiv.0906.3749 (lo cité en mi pieza LCMF, 23 jun 2009). Si como homenaje a los 60 años de la función castor afanoso quieres leer la publicación original, te recuerdo que es Tibor Radó, «On Non-Computable Functions,» Bell System Technical Journal 41: 877-884 (May 1962), doi: https://doi.org/10.1002/j.1538-7305.1962.tb00480.x (PDF). También te recomiendo   Shen Lin, Tibor Rado, «Computer Studies of Turing Machine Problems,» Journal of the ACM 12: 196-212 (1965), doi: https://doi.org/10.1145/321264.321270 (PDF).

Esta entrada participa en la Edición 13.2: Johann Faulhaber del Carnaval de Matemáticas (@CarnaMat), que en esta ocasión organiza Miguel Ángel Morales Medina en su blog Gaussianos. Puedes participar del 5 al 15 de mayo de 2022. ¡Anímate!

[PS 07 jul 2023] Por cierto, hay múltiples variantes de la función castor afanoso, como las que presentaron Scott Aaronson, «Striking new Beeping Busy Beaver champion,» Shtetl-Optimized, 27 Jul 2021; Nick Drozd, «A New Record in Self-Cleaning Turing Machines,» Something Something Programming, 11 Jul 2021; ND, «Structured Programming for Busy Beavers,» SSP, 21 Apr 2021; ND, «A Mathematical Fact from a Busy Beaver,» SSP, 12 Apr 2021; ND, «Halt, Quasihalt, Recur,» SSP, 14 Jan 2021; «Beeping Busy Beaver Results,» SSP, 09 Oct 2020.

Aaronson introdujo una variante llamada Beeping Busy Beaver (BBB) inspirada en una sugerencia de Harvey Friedman: la máquina de Turing con pitido (beeping Turing machine) es una que tiene un estado (único) que emite un pitido (beep). La función BBB(n) se define como el mayor número de pitidos que puede emitir una máquina de Turing con pitido con n estados. Aaronson demostró que BBB(1) = 1 = BB(1), BBB(2) = 6 = BB(2), BBB(3) ≥ 55 > 21 = BB(3) y que BBB(4) ≥ 2,819 > 107 = BB(4). Recientemente se ha confirmado que BBB(3) = 55 y que BBB(4) ≥ 32 779 478. [/PS]

Tibor Radó nació en Budapest (Hungría) el 2 de junio de 1895, y falleció en Florida (EE.UU.) el 29 de diciembre de 1965. Estudió Ingeniería Civil en el Instituto Politécnico de Budapest. Durante la Primera Guerra Mundial fue capturado por los rusos y pasó cuatro años en un campo de prisioneros de guerra. Allí conoció al matemático Eduard Helly, que le enseñó matemáticas y le animó a realizar un doctorado. Regresó a Hungría en 1920, donde realizó su tesis de doctorado bajo la dirección de Riesz y Fejér (la defendió en 1922). En 1929 emigró a Estados Unidos y en 1930 fue nombrado profesor en la Universidad Estatal de Ohio (donde permaneció hasta su jubilación en 1965).

El trabajo de investigación más famoso de Radó fue la resolución del problema de Plateau (planteado por Lagrange en 1760, fue aplicado a pompas de jabón por Plateau): encontrar la superficie de área mínima con una frontera dada (que sea una curva simple cerrada, sin nudos, en el espacio tridimensional). Si te interesa este problema te recomiendo el excelente libritdo de Frederick J. Almgren, «Plateau’s Problem: an Invitation to Varifold Geometry,» AMS (1966). Radó trabajó en muchas áreas de las matemáticas (desde variable compleja a geometría diferencial, pasando por cálculo de variaciones, ecuaciones en derivadas parciales y análisis real, entre otras).

A principios de los 1960, Radó se interesó por la informática teórica y, en particular, por las máquinas de Turing. Se apasionó por las funciones no calculables (o no computables), descubriendo la función castor afanoso. Trabajó con su estudiante Shen Lin en la búsqueda de castores afanosos hasta su jubilación y fallecimiento poco después. Los artículos de Radó destacan por su claridad y por el cuidado de su presentación. Te recomiendo disfrutar sus artículos sobre la función castor afanoso.

La mejor manera de que un aficionado a las matemáticas se ponga a aprender sobre máquinas de Turing es que disponga de un simulador. Cuando yo era estudiante desarrollé uno en C++ que incluía una  interfaz gráfica y un depurador (debugger). En la actualidad imparto clases en R, un lenguaje matemático que se usa mucho en estadística y en bioinformática. Así que os presento una implementación sencilla de dicho simulador en dicho lenguaje. Este código es una modificación trivial del código en C de Nick Drozd, «Are Turing Machines Programmable?» Something Something Programming (SSP), 14 Sep 2020; también te recomiendo su pieza «The Lin-Rado Busy Beaver Proof,» SSP, 15 Dec 2020.

## Simulador de maquinas de Turing en R
## modificado de un codigo de Nick Drozd
##
## 1RB 1RH 1LB 0RC 1LC 1LA 
##
turing.string = "1RB 1RH 1LB 0RC 1LC 1LA";
turing.string = "1RB 1LB 1LA 1RH"; M =10;
turing.string = "1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA"; M = 24; 
##
turing.vector = unlist(strsplit(turing.string," "))
turing.table = matrix(turing.vector,ncol=2,byrow=TRUE)
colnames(turing.table)=c("0","1")
rownames(turing.table)=toupper(letters[1:nrow(turing.table)])
##
tape = rep("0",M); pos = M/2; state = "A";
##
tape.print = tape; tape.print[tape=="0"]="_"; tape.print[tape=="1"]="#"; 
tape.print = c(tape.print[1:(pos-1)],"[",tape.print[pos],"]",tape.print[(pos+1):M]);
## 
tape.matrix = matrix(tape.print,nrow=1); # colnames(tape.matrix)=NULL;
library(stringr)
while (state != "H")
{
SMS = turing.table[state,tape[pos]]; ## Symbol-Movement-State
tape[pos] = substr(SMS,1,1); ## write symbol in tape
pos = pos + switch(1+(substr(SMS,2,2)=="R"),-1,+1); ## move
state = substr(SMS,3,3);
tape.print = tape; tape.print[tape=="0"]="_"; tape.print[tape=="1"]="#"; 
tape.print = c(tape.print[1:(pos-1)],"[",tape.print[pos],"]",tape.print[(pos+1):M]);
tape.matrix = rbind(tape.matrix,tape.print)
}
## Ejemplo de ejecucion de una maquina de Turing
for (ii in 1:nrow(tape.matrix))
print(paste0(c(str_pad(ii, 3, pad = "0"),":",tape.matrix[ii,]),collapse=""),digits=3)
##

El resultado de este código es el siguiente (la salida no es gráficamente muy bonita y animo a los interesados a mejorarla).

>
[1] "001:___________[_]____________"
[1] "002:___________|<_>___________"
[1] "003:___________<|>|___________"
[1] "004:__________<_>||___________"
[1] "005:_________<_>|||___________"
...
[1] "105:__|<|>|||||||||||_________"
[1] "106:__<|>||||||||||||_________"
[1] "107:_<_>_||||||||||||_________"
[1] "108:_|<_>||||||||||||_________"
>

Lo dicho, mi intención es animarte a jugar con máquinas de Turing y a disfrutar buscando castores afanosos. Si te atreves a embarcarte en la aventura, ¡qué lo disfrutes!



2 Comentarios

  1. Francis aquí te dejo cómo representar la salida con plotly.

    Otros intentos en https://www.bitfoam.com/post/turing-machines-and-the-busy-beavers/

    ## Turing Machine Simulator in R
    ## Based on Francis’, in turn, based on Nick Drozd’s code
    ##
    ## This 4-state busy beaver was proven by Allen Brady in 1983.
    ##
    turing.string = «1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA»;
    M = 24;
    ##
    turing.vector = unlist(strsplit(turing.string,» «))
    turing.table = matrix(turing.vector,ncol=2,byrow=TRUE)
    colnames(turing.table)=c(«0″,»1»)
    rownames(turing.table)=toupper(letters[1:nrow(turing.table)])
    ##
    tape = rep(0,M);
    pos = M/2;
    state = «A»;
    ##
    tape.print = tape;
    tape.print[tape==0]=0;
    tape.print[tape==1]=1;
    tape.print = c(tape.print[1:(pos-1)],tape.print[pos] + 2 ,tape.print[(pos+1):M]);
    ##
    tape.matrix = matrix(tape.print,nrow=1);
    library(stringr)
    while (state != «H») # H represents the Halt state
    {
    SMS = turing.table[state, as.character(tape[pos])]; ## Symbol-Movement-State
    tape[pos] = as.integer(substr(SMS,1,1)); ## write symbol in tape
    pos = pos + switch(1+(substr(SMS,2,2)==»R»),-1,+1); ## move Right or Left
    state = substr(SMS,3,3);
    tape.print = tape;
    tape.print[tape==0]=0;
    tape.print[tape==1]=1;
    tape.print = c(tape.print[1:(pos-1)],tape.print[pos] + 2 ,tape.print[(pos+1):M]);
    tape.matrix = rbind(tape.matrix,tape.print)
    }

    library(plotly)
    library(dplyr)

    colorScale <- data.frame(z=c(0,0.25,
    0.25,0.5,
    0.5,0.75,
    0.75,1
    ),col=c('white','white','orange','orange','gray','gray','red','red'))
    colorScale$col <- as.character(colorScale$col)

    fig <- plot_ly(z = tape.matrix,
    type = "heatmap",
    ygap=1,
    xgap=1,
    colorscale=colorScale ,
    width=300, height=600)

    fig %
    config(displayModeBar = FALSE, scrollZoom = FALSE) %>%
    layout(plot_bgcolor=’#ffff’, autosize = F,
    xaxis = list(
    constrain=»domain»,
    title=’Tape’,
    ticks = »,
    tickvals = »,
    range=c(0,M -1)
    ),
    yaxis = list(
    title=’Step’,
    autorange = ‘reversed’,
    scaleanchor = «x»,
    scaleratio = 0.8,
    tickmode = ‘linear’,
    dtick = 1,
    tickfont = list(size=8)
    ),
    showlegend = F) %>%
    colorbar(title = ‘Tape cell’,
    len=0.2,
    dtick =1,
    tickvals=c(0.5,1.25,2,2.75),
    ticktext=c(» 0 «,» 1 «,»[0]»,»[1]»))

    fig

Deja un comentario