$null_symbol = '_'
 
code_example = """ 
_ 1 => _ L 2
_ 4 => _ N 0
_ 5 => _ N 0
a 1 => a R 1
a 2 => a L 3
a 3 => _ L 4
a 4 => _ L 4
a 5 => b L 5
b 1 => b R 1
b 2 => b L 3
b 3 => b L 5
b 4 => _ L 4
b 5 => b L 5
""" #"
 
code_311 = """ 
a 1 => _ R 10
b 1 => _ R 20
 
a 10 => a R 11
a 20 => a R 21
b 10 => b R 11
b 20 => b R 21
_ 10 => _ R 11
_ 20 => _ R 21
 
a 11 => a R 12
a 21 => a R 22
b 11 => a R 12
b 21 => a R 22
_ 11 => a R 12
_ 21 => a R 22
 
a 12 => a R 3
a 22 => b R 3
b 12 => a R 3
b 22 => b R 3
_ 12 => a R 3
_ 22 => b R 3
 
a 3 => _ R 3
b 3 => _ R 3
_ 3 => _ N 0
""" #"
 
code_312 = """
1 1 => 1 R 1
_ 1 => S N 10
 
S 10 => S R 11
_ 11 => _ L 30
1 11 => 1 L 12
S 12 => S L 13
_ 13 => _ R 20
1 13 => 1 R 14
S 14 => S N 40
 
S 20 => _ R 21
1 21 => _ R 21
_ 21 => _ N 0
 
S 30 => 1 L 31
1 31 => _ L 31
_ 31 => _ N 0
 
S 40 => S L 41
1 41 => 1 L 41
_ 41 => _ R 42
1 42 => _ R 43
1 43 => 1 R 43
S 43 => S R 44
1 44 => 1 R 44
_ 44 => _ L 45
1 45 => _ L 46
1 46 => 1 L 46
S 46 => S N 10
""" #"
 
code_313 = """
1 1 => _ R 1
1 2 => 1 R 2
1 3 => _ R 3
1 4 => _ L 5
1 5 => 1 L 5
_ 1 => 1 R 2
_ 2 => 1 R 3
_ 3 => _ R 4
_ 4 => _ L 4
_ 5 => 1 L 6
_ 6 => 1 L 0
""" #"
 
class TuringMachine
  class TuringMachineWord
    attr_accessor :low_bound, :high_bound, :by_index
 
    def initialize(wrd)
      @low_bound, @high_bound = 0, wrd.length-1
      @by_index = Hash.new
      wrd.length.times {|i| @by_index[i] = wrd[i]}
    end
 
    def to_s
      res = []
      for i in (@low_bound-1..@high_bound+1) do
        res << (@by_index[i] || $null_symbol)
      end
      res.join ''
    end
 
    def []=(key, value)
      @by_index[key] = value
      @low_bound  = [@low_bound,  key].min
      @high_bound = [@high_bound, key].max 
    end
 
    def [](key)
      @by_index[key]
    end
  end
 
  attr_accessor :commands, :state, :word, :pos, :step_count, :finished
  attr_accessor :name
 
  def initialize(name='Custom Turing machine')
    @commands = Hash.new
    @name = name
  end
 
  def set_com(com)
    com = parse_com com
    unless com
      log 'Invalid command'
      return
    end
 
    @commands[com[0]] = com[1]
  end
 
  def log(msg='')
    puts "[TM] " + msg
  end
 
  def run(wrd)
    @word = TuringMachineWord.new wrd
    @state, @pos, @step_count = 1, 0, 0
    @finished = false
 
    log "Starting #{@name} on a word '#{wrd}'..."
    log "Initial:"
    log_step
 
    step until @finished
 
    log "Finished #{@name} run."
  end
 
  private
  def parse_com(com)
    com = com.split(' => ').map &:split
    return false unless 
        com.length == 2 && 
        com[0].length == 2 && 
        com[1].length == 3 &&
        /^[LNR]$/ =~ com[1][1]
 
    com[1][1] = 'LNR'.index(com[1][1])-1
    2.times {|i| com[i][-1] = com[i][-1].to_i}
    com
  end
 
  def step
    com = @commands[[@word[@pos] || $null_symbol, @state]]
 
    unless com
      log "No command for state [#{@word[@pos]}, #{@state}]"
      @finished = true
      return
    end
 
    @word[@pos] = com[0]
    @pos += com[1]
    @state = com[2]
    @finished = true if @state == 0
 
    @step_count += 1
    log "Step: #{@step_count}"
    log_step
  end
 
  def log_step
    log @word.to_s
    log ' '*(@pos - @word.low_bound + 1) + "^ #{@state}"
    log
  end
 
end
 
puts """
Turing machine emulator
 
Commands to enter must be in format: 
    'symbol state => new_symbol [LNR] new_state'
 
L - shift left, N - stay in position, R - shift right
Null-symbol (lambda) is #{$null_symbol}
 
Choose Turing machine:
    0) custom machine
    1) 3.1.1 example (any [ab]+ word into [x(n) if x(n-1)=a else b*(n-1)+x(n)])
    2) 3.1.1 variant 5 (any [ab]+ word into x(2)ax(1))
    3) 3.1.2 variant 5 (f(x,y) => (x >= y) ? 1 : 0)
    4) 3.1.3 variant 5 (set by table, x(2) + x(3) + 2)
""" #"
 
case gets.strip
when '1'
  tm = TuringMachine.new '3.1.1 example'
  code_example.each_line do |line| 
    tm.set_com line.strip unless line.strip == ''
  end
when '2'
  tm = TuringMachine.new 'variant 5 (3.1.1)'
  code_311.each_line do |line| 
    tm.set_com line.strip unless line.strip == ''
  end
when '3'
  tm = TuringMachine.new 'variant 5 (3.1.2)'
  code_312.each_line do |line| 
    tm.set_com line.strip unless line.strip == ''
  end
when '4'
  tm = TuringMachine.new 'variant 5 (3.1.3)'
  code_313.each_line do |line| 
    tm.set_com line.strip unless line.strip == ''
  end
when '0' 
  tm = TuringMachine.new
  puts "Enter amount of commands and then list of commands:"
  gets.strip.to_i.times do |_| 
    line = gets.strip
    tm.set_com line unless line == ''
  end
else
  puts 'Invalid option'
  exit
end
 
while true do
  puts "Enter word:"
  tm.run gets.strip
end

JG51bGxfc3ltYm9sID0gJ18nCgpjb2RlX2V4YW1wbGUgPSAiIiIgCl8gMSA9PiBfIEwgMgpfIDQgPT4gXyBOIDAKXyA1ID0+IF8gTiAwCmEgMSA9PiBhIFIgMQphIDIgPT4gYSBMIDMKYSAzID0+IF8gTCA0CmEgNCA9PiBfIEwgNAphIDUgPT4gYiBMIDUKYiAxID0+IGIgUiAxCmIgMiA9PiBiIEwgMwpiIDMgPT4gYiBMIDUKYiA0ID0+IF8gTCA0CmIgNSA9PiBiIEwgNQoiIiIgIyIKCmNvZGVfMzExID0gIiIiIAphIDEgPT4gXyBSIDEwCmIgMSA9PiBfIFIgMjAKCmEgMTAgPT4gYSBSIDExCmEgMjAgPT4gYSBSIDIxCmIgMTAgPT4gYiBSIDExCmIgMjAgPT4gYiBSIDIxCl8gMTAgPT4gXyBSIDExCl8gMjAgPT4gXyBSIDIxCgphIDExID0+IGEgUiAxMgphIDIxID0+IGEgUiAyMgpiIDExID0+IGEgUiAxMgpiIDIxID0+IGEgUiAyMgpfIDExID0+IGEgUiAxMgpfIDIxID0+IGEgUiAyMgoKYSAxMiA9PiBhIFIgMwphIDIyID0+IGIgUiAzCmIgMTIgPT4gYSBSIDMKYiAyMiA9PiBiIFIgMwpfIDEyID0+IGEgUiAzCl8gMjIgPT4gYiBSIDMKCmEgMyA9PiBfIFIgMwpiIDMgPT4gXyBSIDMKXyAzID0+IF8gTiAwCiIiIiAjIgoKY29kZV8zMTIgPSAiIiIKMSAxID0+IDEgUiAxCl8gMSA9PiBTIE4gMTAKClMgMTAgPT4gUyBSIDExCl8gMTEgPT4gXyBMIDMwCjEgMTEgPT4gMSBMIDEyClMgMTIgPT4gUyBMIDEzCl8gMTMgPT4gXyBSIDIwCjEgMTMgPT4gMSBSIDE0ClMgMTQgPT4gUyBOIDQwCgpTIDIwID0+IF8gUiAyMQoxIDIxID0+IF8gUiAyMQpfIDIxID0+IF8gTiAwCgpTIDMwID0+IDEgTCAzMQoxIDMxID0+IF8gTCAzMQpfIDMxID0+IF8gTiAwCgpTIDQwID0+IFMgTCA0MQoxIDQxID0+IDEgTCA0MQpfIDQxID0+IF8gUiA0MgoxIDQyID0+IF8gUiA0MwoxIDQzID0+IDEgUiA0MwpTIDQzID0+IFMgUiA0NAoxIDQ0ID0+IDEgUiA0NApfIDQ0ID0+IF8gTCA0NQoxIDQ1ID0+IF8gTCA0NgoxIDQ2ID0+IDEgTCA0NgpTIDQ2ID0+IFMgTiAxMAoiIiIgIyIKCmNvZGVfMzEzID0gIiIiCjEgMSA9PiBfIFIgMQoxIDIgPT4gMSBSIDIKMSAzID0+IF8gUiAzCjEgNCA9PiBfIEwgNQoxIDUgPT4gMSBMIDUKXyAxID0+IDEgUiAyCl8gMiA9PiAxIFIgMwpfIDMgPT4gXyBSIDQKXyA0ID0+IF8gTCA0Cl8gNSA9PiAxIEwgNgpfIDYgPT4gMSBMIDAKIiIiICMiCgpjbGFzcyBUdXJpbmdNYWNoaW5lCiAgY2xhc3MgVHVyaW5nTWFjaGluZVdvcmQKICAgIGF0dHJfYWNjZXNzb3IgOmxvd19ib3VuZCwgOmhpZ2hfYm91bmQsIDpieV9pbmRleAogICAgCiAgICBkZWYgaW5pdGlhbGl6ZSh3cmQpCiAgICAgIEBsb3dfYm91bmQsIEBoaWdoX2JvdW5kID0gMCwgd3JkLmxlbmd0aC0xCiAgICAgIEBieV9pbmRleCA9IEhhc2gubmV3CiAgICAgIHdyZC5sZW5ndGgudGltZXMge3xpfCBAYnlfaW5kZXhbaV0gPSB3cmRbaV19CiAgICBlbmQKICAgIAogICAgZGVmIHRvX3MKICAgICAgcmVzID0gW10KICAgICAgZm9yIGkgaW4gKEBsb3dfYm91bmQtMS4uQGhpZ2hfYm91bmQrMSkgZG8KICAgICAgICByZXMgPDwgKEBieV9pbmRleFtpXSB8fCAkbnVsbF9zeW1ib2wpCiAgICAgIGVuZAogICAgICByZXMuam9pbiAnJwogICAgZW5kCiAgICAKICAgIGRlZiBbXT0oa2V5LCB2YWx1ZSkKICAgICAgQGJ5X2luZGV4W2tleV0gPSB2YWx1ZQogICAgICBAbG93X2JvdW5kICA9IFtAbG93X2JvdW5kLCAga2V5XS5taW4KICAgICAgQGhpZ2hfYm91bmQgPSBbQGhpZ2hfYm91bmQsIGtleV0ubWF4IAogICAgZW5kCiAgICAKICAgIGRlZiBbXShrZXkpCiAgICAgIEBieV9pbmRleFtrZXldCiAgICBlbmQKICBlbmQKICAKICBhdHRyX2FjY2Vzc29yIDpjb21tYW5kcywgOnN0YXRlLCA6d29yZCwgOnBvcywgOnN0ZXBfY291bnQsIDpmaW5pc2hlZAogIGF0dHJfYWNjZXNzb3IgOm5hbWUKICAKICBkZWYgaW5pdGlhbGl6ZShuYW1lPSdDdXN0b20gVHVyaW5nIG1hY2hpbmUnKQogICAgQGNvbW1hbmRzID0gSGFzaC5uZXcKICAgIEBuYW1lID0gbmFtZQogIGVuZAogIAogIGRlZiBzZXRfY29tKGNvbSkKICAgIGNvbSA9IHBhcnNlX2NvbSBjb20KICAgIHVubGVzcyBjb20KICAgICAgbG9nICdJbnZhbGlkIGNvbW1hbmQnCiAgICAgIHJldHVybgogICAgZW5kCiAgICAKICAgIEBjb21tYW5kc1tjb21bMF1dID0gY29tWzFdCiAgZW5kCiAgCiAgZGVmIGxvZyhtc2c9JycpCiAgICBwdXRzICJbVE1dICIgKyBtc2cKICBlbmQKICAKICBkZWYgcnVuKHdyZCkKICAgIEB3b3JkID0gVHVyaW5nTWFjaGluZVdvcmQubmV3IHdyZAogICAgQHN0YXRlLCBAcG9zLCBAc3RlcF9jb3VudCA9IDEsIDAsIDAKICAgIEBmaW5pc2hlZCA9IGZhbHNlCiAgICAKICAgIGxvZyAiU3RhcnRpbmcgI3tAbmFtZX0gb24gYSB3b3JkICcje3dyZH0nLi4uIgogICAgbG9nICJJbml0aWFsOiIKICAgIGxvZ19zdGVwCiAgICAKICAgIHN0ZXAgdW50aWwgQGZpbmlzaGVkCiAgICAKICAgIGxvZyAiRmluaXNoZWQgI3tAbmFtZX0gcnVuLiIKICBlbmQKICAKICBwcml2YXRlCiAgZGVmIHBhcnNlX2NvbShjb20pCiAgICBjb20gPSBjb20uc3BsaXQoJyA9PiAnKS5tYXAgJjpzcGxpdAogICAgcmV0dXJuIGZhbHNlIHVubGVzcyAKICAgICAgICBjb20ubGVuZ3RoID09IDIgJiYgCiAgICAgICAgY29tWzBdLmxlbmd0aCA9PSAyICYmIAogICAgICAgIGNvbVsxXS5sZW5ndGggPT0gMyAmJgogICAgICAgIC9eW0xOUl0kLyA9fiBjb21bMV1bMV0KICAgIAogICAgY29tWzFdWzFdID0gJ0xOUicuaW5kZXgoY29tWzFdWzFdKS0xCiAgICAyLnRpbWVzIHt8aXwgY29tW2ldWy0xXSA9IGNvbVtpXVstMV0udG9faX0KICAgIGNvbQogIGVuZAogIAogIGRlZiBzdGVwCiAgICBjb20gPSBAY29tbWFuZHNbW0B3b3JkW0Bwb3NdIHx8ICRudWxsX3N5bWJvbCwgQHN0YXRlXV0KICAgIAogICAgdW5sZXNzIGNvbQogICAgICBsb2cgIk5vIGNvbW1hbmQgZm9yIHN0YXRlIFsje0B3b3JkW0Bwb3NdfSwgI3tAc3RhdGV9XSIKICAgICAgQGZpbmlzaGVkID0gdHJ1ZQogICAgICByZXR1cm4KICAgIGVuZAogICAgCiAgICBAd29yZFtAcG9zXSA9IGNvbVswXQogICAgQHBvcyArPSBjb21bMV0KICAgIEBzdGF0ZSA9IGNvbVsyXQogICAgQGZpbmlzaGVkID0gdHJ1ZSBpZiBAc3RhdGUgPT0gMAogICAgCiAgICBAc3RlcF9jb3VudCArPSAxCiAgICBsb2cgIlN0ZXA6ICN7QHN0ZXBfY291bnR9IgogICAgbG9nX3N0ZXAKICBlbmQKICAKICBkZWYgbG9nX3N0ZXAKICAgIGxvZyBAd29yZC50b19zCiAgICBsb2cgJyAnKihAcG9zIC0gQHdvcmQubG93X2JvdW5kICsgMSkgKyAiXiAje0BzdGF0ZX0iCiAgICBsb2cKICBlbmQKICAKZW5kCgpwdXRzICIiIgpUdXJpbmcgbWFjaGluZSBlbXVsYXRvcgoKQ29tbWFuZHMgdG8gZW50ZXIgbXVzdCBiZSBpbiBmb3JtYXQ6IAogICAgJ3N5bWJvbCBzdGF0ZSA9PiBuZXdfc3ltYm9sIFtMTlJdIG5ld19zdGF0ZScKCkwgLSBzaGlmdCBsZWZ0LCBOIC0gc3RheSBpbiBwb3NpdGlvbiwgUiAtIHNoaWZ0IHJpZ2h0Ck51bGwtc3ltYm9sIChsYW1iZGEpIGlzICN7JG51bGxfc3ltYm9sfQoKQ2hvb3NlIFR1cmluZyBtYWNoaW5lOgogICAgMCkgY3VzdG9tIG1hY2hpbmUKICAgIDEpIDMuMS4xIGV4YW1wbGUgKGFueSBbYWJdKyB3b3JkIGludG8gW3gobikgaWYgeChuLTEpPWEgZWxzZSBiKihuLTEpK3gobildKQogICAgMikgMy4xLjEgdmFyaWFudCA1IChhbnkgW2FiXSsgd29yZCBpbnRvIHgoMilheCgxKSkKICAgIDMpIDMuMS4yIHZhcmlhbnQgNSAoZih4LHkpID0+ICh4ID49IHkpID8gMSA6IDApCiAgICA0KSAzLjEuMyB2YXJpYW50IDUgKHNldCBieSB0YWJsZSwgeCgyKSArIHgoMykgKyAyKQoiIiIgIyIKCmNhc2UgZ2V0cy5zdHJpcAp3aGVuICcxJwogIHRtID0gVHVyaW5nTWFjaGluZS5uZXcgJzMuMS4xIGV4YW1wbGUnCiAgY29kZV9leGFtcGxlLmVhY2hfbGluZSBkbyB8bGluZXwgCiAgICB0bS5zZXRfY29tIGxpbmUuc3RyaXAgdW5sZXNzIGxpbmUuc3RyaXAgPT0gJycKICBlbmQKd2hlbiAnMicKICB0bSA9IFR1cmluZ01hY2hpbmUubmV3ICd2YXJpYW50IDUgKDMuMS4xKScKICBjb2RlXzMxMS5lYWNoX2xpbmUgZG8gfGxpbmV8IAogICAgdG0uc2V0X2NvbSBsaW5lLnN0cmlwIHVubGVzcyBsaW5lLnN0cmlwID09ICcnCiAgZW5kCndoZW4gJzMnCiAgdG0gPSBUdXJpbmdNYWNoaW5lLm5ldyAndmFyaWFudCA1ICgzLjEuMiknCiAgY29kZV8zMTIuZWFjaF9saW5lIGRvIHxsaW5lfCAKICAgIHRtLnNldF9jb20gbGluZS5zdHJpcCB1bmxlc3MgbGluZS5zdHJpcCA9PSAnJwogIGVuZAp3aGVuICc0JwogIHRtID0gVHVyaW5nTWFjaGluZS5uZXcgJ3ZhcmlhbnQgNSAoMy4xLjMpJwogIGNvZGVfMzEzLmVhY2hfbGluZSBkbyB8bGluZXwgCiAgICB0bS5zZXRfY29tIGxpbmUuc3RyaXAgdW5sZXNzIGxpbmUuc3RyaXAgPT0gJycKICBlbmQKd2hlbiAnMCcgCiAgdG0gPSBUdXJpbmdNYWNoaW5lLm5ldwogIHB1dHMgIkVudGVyIGFtb3VudCBvZiBjb21tYW5kcyBhbmQgdGhlbiBsaXN0IG9mIGNvbW1hbmRzOiIKICBnZXRzLnN0cmlwLnRvX2kudGltZXMgZG8gfF98IAogICAgbGluZSA9IGdldHMuc3RyaXAKICAgIHRtLnNldF9jb20gbGluZSB1bmxlc3MgbGluZSA9PSAnJwogIGVuZAplbHNlCiAgcHV0cyAnSW52YWxpZCBvcHRpb24nCiAgZXhpdAplbmQKCndoaWxlIHRydWUgZG8KICBwdXRzICJFbnRlciB3b3JkOiIKICB0bS5ydW4gZ2V0cy5zdHJpcAplbmQ=

NAoxXzEK

4
1_1