Turing machines and the busy beavers

For years I have been an avid reader of the Science website Naukas. The website is a carrier for online science popularization in Spanish. If you speak the language and love Science, I greatly encourage you to add it to your bookmarks.

In particular, I am a big (BIG) fan of Francis’ blog as well as Daniel’s blog that are part of the Naukas family.

I must admit that they have been an inspiration for the creation of this micro-blog. So, when I came across the article “Carnaval de Matemáticas: La función castor afanoso cumple 60 años” (Villatorio 2022) and the R code snippet of a Turing Machine simulator and a Busy Beaver, I couldn’t help but put together this small post and explore how to represent the Busy Beaver output using R.

Turing Machines

The Wikipedia (Wikipedia contributors 2022b) provides an excellent overview about the Turing Machines.

While some details may vary depending on the definition, basically, a Turing machine is an abstract machine - or theoretical model - consisting of :

  • An infinite tape divided into cells. Each cell contains a symbol from a finite alphabet.
  • A head that can read (scan) the symbol on the tape under the head or write a new symbol. The head can shift one cell at a time to either (L)eft or (R)ight.
  • A state register that stores the current state.
  • A table of instructions (states).

A new state is derived from the combination of the symbol in the tape and the current state, the machine runs till it reaches the state “H” (Halt).

Busy Beaver

Francis’ article (Villatorio 2022) is about Tibor Radó who discovered the Busy Beaver functions, a type of Turing machines, in 1962 (Rado 1962) and provides a brief context on the topic as well as the main references.

Below I bring over a simple description from Wikipedia to share some context.

… the busy beaver game consists of designing a halting Turing machine with alphabet {0,1} which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows:

The website Turing Machine Visualization is of great assistance in visualising Turing machines. Among others you can simulate and visualise a 3-state and 4-state Busy Beaver.

Next I share the code taken from Francis’ article with some minor changes.

 1## Turing Machine Simulator in R
 2## Based on Francis', in turn, based on Nick Drozd's code
 3##
 4## This 4-state busy beaver was proven by Allen Brady in 1983.
 5##
 6turing.string = '1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA'; 
 7M = 24; 
 8##
 9turing.vector = unlist(strsplit(turing.string,' '))
10turing.table = matrix(turing.vector,ncol=2,byrow=TRUE)
11colnames(turing.table)=c('0','1')
12rownames(turing.table)=toupper(letters[1:nrow(turing.table)])
13
14library(knitr)
15kable(t(turing.table), caption = 'Table of states (instructions) of 4-state 2-symbol Busy Beaver')
Table 1: 4-state 2-symbol Busy Beaver: Table of states (instructions)
A B C D
0 1RB 1LA 1RH 1RD
1 1LB 0LC 1LD 0RA

I have changed the code to generate a numeric matrix describing the tape for each step ,from top to bottom, untils the machine halts, the numbers in the matrix hold the following meanings:

  • 0: symbol 0 in cell
  • 1: symbo1 1 in cell
  • 2: head on symbol 0 in cell
  • 3: head on symbol 1 in cell
 1##
 2tape = rep(0,M); 
 3pos = M/2; 
 4state = 'A';
 5##
 6tape.print = tape;
 7tape.print[tape==0]=0; 
 8tape.print[tape==1]=1; 
 9tape.print = c(tape.print[1:(pos-1)],tape.print[pos] + 2 ,tape.print[(pos+1):M]);
10## 
11tape.matrix = matrix(tape.print,nrow=1);
12library(stringr)
13while (state != 'H') # H represents the Halt state
14{
15  SMS = turing.table[state, as.character(tape[pos])]; ## Symbol-Movement-State
16  tape[pos] = as.integer(substr(SMS,1,1));            ## write symbol in tape
17  pos = pos + switch(1+(substr(SMS,2,2)=='R'),-1,+1); ## move Right or Left
18  state = substr(SMS,3,3);
19  tape.print = tape; 
20  tape.print[tape==0]=0; 
21  tape.print[tape==1]=1; 
22  tape.print = c(tape.print[1:(pos-1)],tape.print[pos] + 2 ,tape.print[(pos+1):M]);
23  tape.matrix = rbind(tape.matrix,tape.print)
24}

Goal

Francis in his article raised a request for finding a better representation of the output of the 4-state 2-symbol Busy Beaver function.

In Wikipedia one comes across the following representation of a 3-state Busy Beaver (Commons 2021):

3-state Busy Beaver. Black icons represent location and state of head; square colors represent 1s (orange) and 0s (white); time progresses vertically from the top until the HALT state at the bottom.

Figure 1: 3-state Busy Beaver. Black icons represent location and state of head; square colors represent 1s (orange) and 0s (white); time progresses vertically from the top until the HALT state at the bottom.

This figure is used as a model for the the representations in this post.

Using plot.matrix

Below represents the very first attempt using the library plot.matrix.

1#install.packages('plot.matrix')
2library('plot.matrix' )
3plot(tape.matrix ,col = c('white','orange','grey','red'), key=NULL,axis.col = NULL,  axis.row= NULL, xlab='Tape', ylab='Steps', border=NA,polygon.cell = NULL)

This has been very easy, however I have found it difficult to apply further changes.

Using plotly

The second and most successful attempt so far is using plotly (Sievert 2020).

The challenge is getting a discrete colorbar so that one discrete colour is assign to the possible cell values. The article shares the trick to get this precisely.

 1library(plotly)
 2library(dplyr)
 3
 4colorScale <- data.frame(z=c(0,0.25,
 5                             0.25,0.5,
 6                             0.5,0.75,
 7                             0.75,1
 8               ),col=c('white','white','orange','orange','gray','gray','red','red'))
 9colorScale$col <- as.character(colorScale$col)
10
11fig <- plot_ly(z = tape.matrix,
12               type = 'heatmap',
13               ygap=1,
14               xgap=1,
15               colorscale=colorScale ,
16               width=300, height=600)
17
18fig <- fig  %>% 
19  config(displayModeBar = FALSE, scrollZoom = FALSE) %>%
20  layout(plot_bgcolor='rgb(0,0,0)', 
21             autosize = F,
22             xaxis = list(
23               constrain='domain',
24               title='Tape',
25               ticks = '',
26               tickvals = '',
27               range=c(0,M -1)
28               ),
29             yaxis = list(
30               title='Step',
31               autorange = 'reversed',
32               scaleanchor = 'x',
33               scaleratio = 0.8,
34               tickmode = 'linear',
35               dtick = 1,
36               tickfont = list(size=8)
37               ),
38             showlegend = F) %>% 
39  colorbar(title = 'Tape cell',
40           len=0.2, 
41           dtick =1,
42           tickvals=c(0.5,1.25,2,2.75), 
43           ticktext=c(' 0 ',' 1 ','[0]','[1]')) 
44
45fig

So far, this approach has taken me closer to what I had in mind and within reasonable time. It hasn´t been easy or quick but I found the details I needed to move on.

Using ggplot2

And finally, ggplot2(Wickham 2016).

 1library(dplyr)
 2library(reshape2)
 3df <- as_data_frame(tape.matrix)
 4df <- df %>% mutate(step = as.integer(rownames(df)))
 5df1 <- melt(df, id.vars = 'step')
 6df1<- df1 %>% mutate(value = factor(value))
 7
 8fig3 <- ggplot(df1, aes(x = variable, y = step))  + 
 9  geom_tile(aes(fill = value),colour = 'black') + 
10  scale_y_reverse(breaks=seq(nrow(tape.matrix) - 1,0,-1)) +
11  coord_fixed(ratio=0.7) + 
12  xlab('Tape') + 
13  theme_minimal() +
14  theme(axis.text.x=element_blank(),axis.ticks.x=element_blank(), axis.text = element_text(size = 3),legend.text = element_text(size = 5),legend.title = element_text(size = 6)) + 
15  scale_x_discrete(breaks=NULL) + 
16  scale_fill_manual(values=c('white','orange','grey','red'),name = 'Tape cell', labels = c('0', '1', '[0]','[1]')) 
17fig3

With ggplot2 it took more less the same time to plot as plotly, however bear in mind that both do not deliver the same type of visulation. Preparing the data took definately longer.

References

Commons, Wikimedia. 2021. “File:busy Beaver 3 State.png — Wikimedia Commons, the Free Media Repository.” \url{https://commons.wikimedia.org/w/index.php?title=File:Busy_Beaver_3_State.png&oldid=531671843}.
Rado, T. 1962. “On Non-Computable Functions.” Bell System Technical Journal 41 (3): 877–84. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x.
Sievert, Carson. 2020. Interactive Web-Based Data Visualization with r, Plotly, and Shiny. Chapman; Hall/CRC. https://plotly-r.com.
Villatorio, Francisco R. 2022. “Carnaval de Matemáticas: La Función Castor Afanoso Cumple 60 Años.” 2022. https://francis.naukas.com/2022/05/14/carnaval-de-matematicas-la-funcion-castor-afanoso-cumple-60-anos/.
Wickham, Hadley. 2016. Ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag New York. https://ggplot2.tidyverse.org.
Wikipedia contributors. 2022a. “Busy Beaver — Wikipedia, the Free Encyclopedia.” https://en.wikipedia.org/w/index.php?title=Busy_beaver&oldid=1087004102.
———. 2022b. “Turing Machine — Wikipedia, the Free Encyclopedia.” https://en.wikipedia.org/w/index.php?title=Turing_machine&oldid=1087872127.
comments powered by Disqus