Chapter 2 Implementing a Turing machine in R

Our goal is to build a Turing machine. First we need a smart encoding of our infinite tape, since R can only use positive indices. We assume that the starting position of our machine is at the left most 1 and let this be position 1. We let the even numbers represent the numbers to the left of our starting position, and the uneven numbers represent the numbers to the right of our starting position.

We define a function for determining the index of a new position, given the current position and the direction:

position_determiner <- function(current_position, direction){
  position <- current_position
  if(current_position == 2 & direction == "R"){position <- position -1 }
  else if(current_position == 1 & direction == "L"){position <- position + 1 }
  else if(current_position %% 2 != 0 & direction == "R"){position <- position + 2} 
  else if(current_position %% 2 == 0 & direction == "R"){position <- position -2 } 
  else if(current_position %% 2 == 0 & direction == "L"){position <- position + 2}
  else{position <- position - 2}
  position}

We can now define our universal turingmachine. The machine takes the program and an input as inputs. The browser argument allows that we can follow the machines course of action step by step, and the ‘numeric’ arguments allows that we get the output as the sum of ones on the tape instead of the tape itself.

turingmachine <- function(program, input, browser = FALSE, numeric = FALSE){
  if(browser){browser()}
  position <-  1
  state <- "1"
  input <- input
  while(state != "0"){
    if(is.na(input[position])){
      input[position] <- program[[state]]$if_read_na$return
      position <- position_determiner(position, program[[state]]$if_read_na$direction)
      state <- program[[state]]$if_read_na$state
    }
    else {
      input[position] <- program[[state]]$if_read_one$return
      position <- position_determiner(position, program[[state]]$if_read_one$direction)
      state <- program[[state]]$if_read_one$state
    }
  }
  if(numeric){sum(as.numeric(input), na.rm = TRUE)} else {as.numeric(input)}
}

In order to ease the usability, we define some functions that can help putting programs and inputs into the correct form, so they are readable by the machine.
We first define a function specifically for creating programs on a correct form such that it can be read by our Turing machine. The function takes a list of vectors and creates a nested list as needed by the machine:

program_builder <- function(list_of_states){
  # function for creating a program that can be read by the turingmachine, 
  # given a list of vectors with the commands
  return_list <- list()
  for(vec in list_of_states){
    loop_list <- list(if_read_na= list(return = vec[2],direction=vec[3],state=vec[4]),
                      if_read_one = list(return = vec[5], direction=vec[6], state=vec[7]))
    return_list[[vec[1]]] <- loop_list 
  }
  return_list
}

We define a function that can create 1d inputs that can be read by our Turing machines:

input_builder_1d <- function(n){
  # function for creating a input that can be read by the turing machine
  output <- c()
  for(i in seq(1,n+1)){
    output <- c(output, 1, NA)
  }
  output
}

We define a function that can create 2d inputs that can be read by our turing machines:

input_builder_2d <- function(n,m){
  # function for creating an  input that can be read by the turing machine
  output <- c()
  for(i in seq(1,n+1)){
    output <- c(output, 1, NA)
  }
  output <- c(output, NA,NA)
  for(i in seq(1,m+1)){
    output <- c(output,1, NA)
  }
  output
}