$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