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 machine must have two states in addition to the halting state, and
• the tape initially contains 0s only.(Wikipedia contributors 2022a)

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')

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):

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.

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)

 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               tick = 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

 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

References