Turing machine simple simulator

turing-machine-simple-simulator.rb

# Turing machine simulator - Inspired by Kill All Software screencast

# Guide to symbols:
# B: Blank. All the values of the tape are initally Blank
# L: Left. For the pointer to move Left
# R: Right. For the pointer to move right
# s{n}: State number {n}, ex. s1, s2, s3

def simulate(instructions)
  # Initial state of the tape
  #
  # In actual turing machines, the tape is infinite, but in practice
  # we can make it arbritarily long
  tape = ['B'] * 16
  state = 's1' # Well the init_state is not fixed, but close enough to the real deal
  pointer = 0
  
  # Run the Program (in the real machine, it's infinite, but I'm keeping 16 iterations)
  32.times do 
    # Print the tape first
    print tape.join('')
    puts
    puts (' ' * pointer) + '^'
    
    # Get value from pointer location
    value = tape[pointer]
    
    result = instructions[[value, state]]
    tape[pointer] = result[0]
    state = result[1]
    
    shift = result[2]
    if(shift == 'L')
      pointer -= 1
    else
      pointer += 1
    end
  end
end

# Program to toggle the first location in the tape between B and X
instructions = {
  ['B', 's1'] => ['X', 's2', 'R'],
  ['B', 's2'] => ['B', 's2', 'L'],
  ['X', 's2'] => ['B', 's3', 'R'],
  ['B', 's3'] => ['B', 's1', 'L']
}
#simulate(instructions)

# Program to add two numbers
# Let's just do positive integers for simplicity
# 
# First a simplistic representation of numbers
# 1: 1
# 2: 11
# 3: 111
# ...
#
# Now to add say, 2 and 5, the tape should look like this
# (11+11111)
# and result in 
# (1111111)
#
# So basically the approach can be converting the plus into a 1, 
# and then reducing the number of 1s from the left 
#
# This is simple, but a proof of concept. Mathematically, the turing machine can do anything
adder = {
  # First init the tape with the two numbers: [3, 4]
  ['B', 's1'] => ['(', 's2', 'R'],
  
  ['B', 's2'] => ['1', 's3', 'R'],
  ['B', 's3'] => ['1', 's4', 'R'],
  ['B', 's4'] => ['1', 's5', 'R'],
  
  ['B', 's5'] => ['+', 's6', 'R'],
  
  ['B', 's6'] => ['1', 's7', 'R'],
  ['B', 's7'] => ['1', 's8', 'R'],
  ['B', 's8'] => ['1', 's9', 'R'],
  ['B', 's9'] => ['1', 's10', 'R'],
  
  ['B', 's10'] => [')', 's11', 'R'],
  
  # Now add the numbers, first go left until the add symbol
  ['B', 's11'] => ['B', 's11', 'L'],
  [')', 's11'] => [')', 's11', 'L'],
  ['1', 's11'] => ['1', 's11', 'L'],
  
  # Hit the add symbol and replace with 1
  ['+', 's11'] => ['1', 's12', 'L'],
  
  # Go left until the opening bracket
  ['1', 's12'] => ['1', 's12', 'L'],
  
  # At opening braket, replace with blank. Then replace 1 on right with opening bracket
  ['(', 's12'] => ['B', 's13', 'R'],
  ['1', 's13'] => ['(', 's14', 'R'],
  ['1', 's14'] => ['HALT'] # I recall some bs about a halt state, but idk the exact definition, so I'm just declaring an arbritary halt

}
simulate(adder)

MIT License