Chapter 3 Examples of Turing programmes

We here present some different example programs that can be used with the Turing machine we have implemented. Note, that they all use the program_builder function we defined in chapter 2, so if you want to play around with them you will need to run the function definition first.
The syntax of each vector is:
(current state, if scan NA print, if scan NA direction, if scan NA new state, if scan 1 print, if scan 1 direction, if scan 1 new state).
In a vector, all elements besides NA must be of same type. Our implementation demands all values different from NA to be quoted. Now lets see some programs.
First we create a program for the function computing \(f(n)=0\):

program_0 <- program_builder(list(c("1",NA,"R","0",NA,"R","1")))

Now we create a program for the function computing \(f(n)=9\). Note that even if this is a simple function, we need quite a lot of states (namely 9). Since the Turing machine has no memory, we need a new state for every time we want to add a 1:

program_9 <- program_builder(list(c("1","1", "R", "2", NA, "R", "1"),
                                  c ("2", "1", "R","3", NA, NA, NA),
                                  c ("3", "1", "R","4", NA, NA, NA),
                                  c ("4", "1", "R","5", NA, NA, NA),
                                  c ("5", "1", "R","6", NA, NA, NA),
                                  c ("6", "1", "R","7", NA, NA, NA),
                                  c ("7", "1", "R","8", NA, NA, NA),
                                  c ("8", "1", "R","9", NA, NA, NA),
                                  c ("9", "1", "R","0", NA, NA, NA)
                                  ))

We create a program for the function computing \(f(n)=2n\).

program_2n <- program_builder(list(
  c("1", NA, NA, NA, NA, "R", "2"), # will always read 1
  c("2", NA, "R","0", NA,"R", "3"),
  c("3", NA, "R", "4", "1", "R", "3"),
  c("4", "1", "R", "5", "1", "R", "4"),
  c("5", "1", "L", "6", NA, NA, NA), # will always read na
  c("6", NA, "L", "7", "1", "L", "6"),
  c("7", NA, "R", "2", "1", "L", "7")
))

We create a program for the function computing \(f(n,m)=n+m\):

program_nplusm <- program_builder(
  list(
    c("1", NA, NA, NA, NA, "R", "2"), # will always read 1
    c("2", NA, "R", "7", NA, "R", "3"),
    c("3", NA, "R", "4", "1", "R", "3"),
    c("4", "1", "L", "5", "1", "R", "4"),
    c("5", NA, "L", "6", "1", "L", "5"),
    c("6", NA, "R", "2", "1", "L", "6"),
    c("7", NA, NA, NA, NA, "R", "0")) # will always read 1
)

We create a program for the function computing \(f(n,m)=n\cdot m\)

program_ntimesm <- program_builder(
  list(
    c("1", NA, NA, NA, NA, "R", "2"), # will always read 1
    c("2", NA, "R", "12", NA, "R", "3"),
    c("3", NA, "R", "4", "1", "R", "3"),
    c("4", NA, NA, NA, "1", "R", "5"),
    c("5", NA, "L", "10", NA, "R", "6"),
    c("6", NA, "R", "7", "1", "R", "6"),
    c("7", "1", "L", "8", "1", "R", "7"),
    c("8", NA, "L", "9", "1", "L", "8"),
    c("9", "1", "R", "5", "1", "L", "9"),
    c("10", NA, "L", "11", "1", "L", "10"),
    c("11", NA, "R", "2", "1", "L", "11"),
    c("12", NA, "R", "0", NA, "R", "12")
  )
)

We create a function computing \(f(n,m)=n\overset{.}{-}m\), truncated minus:

program_nmonusm <- program_builder(
  list(
    c("1", NA, "R", "2", "1", "R", "1"), 
    c("2", NA, "L", "3", "1", "R", "2"),
    c("3", NA, "L", "0", NA, "L", "4"), 
    c("4", NA, "L", "5", "1", "L", "4"),
    c("5", NA, "R", "6", "1", "L", "5"),
    c("6", NA, "R", "7", NA, "R", "1"),
    c("7", NA, "L", "0", NA, "R", "7")
  )
)