# Turing Machine simulator
# with a Fibonacci sequence setup to demo
# 25/12/2013 v2
# Andi Fugard 

newTape = function(initTape = c(" "), pos = 1, state = " ", blank = " ") {
  stopifnot(length(initTape) > 0)
  list(cells = initTape, pos = pos, state = state, blank = blank)
}

tapesEqual = function(t1, t2) {
  length(t1$cells) == length(t2$cells) &&
  t1$cells == t2$cells &&
  t1$pos == t2$pos &&
  t1$state == t2$state &&
  t1$blank == t2$blank
}

runStep = function(tape, quints) {
  quint = subset(quints, s1 == tape$state & i == tape$cells[tape$pos])

  newTape = tape
  if (nrow(quint) == 1) { # relax this when we go nondeterministic
    newTape = tape
    newTape$cells[tape$pos] = quint$o
    newTape$state = quint$s2
    
    stopifnot(quint$d == "L" || quint$d == "R")
    if (quint$d == "R") {
      newTape$pos = newTape$pos + 1
      if (newTape$pos > length(newTape$cells))
        newTape$cells = c(newTape$cells, newTape$blank)
    }
    else if (quint$d == "L") {
      newTape$pos = newTape$pos - 1
      if (newTape$pos < 1) {
        newTape$cells = c(newTape$blank, newTape$cells)
        newTape$pos = 1
      }
    }
  }  

  newTape
}

printTape = function(tape, iteration.number = "") {
  res = rbind(as.character(tape$cells)
             ,rep("", length(tape$cells))
             ,rep("", length(tape$cells)))
  colnames(res) = rep("", length(tape$cells))
  rownames(res) = c(paste("(", iteration.number, ")", sep = ""),"","")

  res[2,tape$pos] = "^"
  res[3,tape$pos] = as.character(tape$state)
  print(res, quote = F)
}

runProgram = function(startTape, program, maxSteps = 10000) {
  printTape(startTape, 0)
  tapeRes = runStep(startTape, program)
  printTape(tapeRes, 1)

  i = 2
  finished = F
  while (i <= maxSteps && !finished) {
    tapeRes.prev = tapeRes
    tapeRes      = runStep(tapeRes.prev, program)

    if (!tapesEqual(tapeRes, tapeRes.prev)) {
      printTape(tapeRes, i)
    }
    else finished = T

    i = i + 1
  }
}

# Fibonaci

fibprog = data.frame(
  s1 = c("A", "A", "B", "B", "C", "C", "D", "D", "E", "E",
       "F", "F", "G", "G", "H", "H", "I", "I", "J",
       "J", "K", "K", "L", "L", "M", "M", "N",
       "N", "O", "O"),
  s2 = c("B", "H", "B", "C", "C", "D", "D", "E", "E", "F",
       "F", "G", "G", "A", "I", "M", "I", "J", "J",
       "K", "K", "L", "L", "H", "M", "N", "N",
       "O", "O", "A"),
  i = c("1", "*", "1", "*", "1", "*", "1", "*", "1", "*", "1", "*",
        "1", "p", "1", "*", "1", "*", "1", "*", "1", "*", "1", "p",
        "p", "*", "p", "*", "1", "*"),
  o = c("p", "*", "1", "*", "1", "*", "1", "1", "1", "*", "1", "*",
        "1", "p", "p", "*", "1", "*", "1", "1", "1", "*", "1", "p",
        "1", "*", "1", "*", "1", "*"),
  d = c("R", "R", "R", "R", "R", "R", "R", "L", "L", "L", "L", "L",
        "L", "R", "R", "L", "R", "R", "R", "L", "L", "L", "L", "R",
        "L", "L", "L", "R", "R", "R"),
  stringsAsFactors = F
)
fibprog 


# Run up 1,1,2,3,5,8 (317 steps)
startTape = newTape(as.character(c(1,"*",1))
                   ,pos = 1
                   ,state = "A"
                   ,blank = "*")
runProgram(startTape, fibprog, maxSteps = 317)