Class: Ntm

Inherits:
Object
  • Object
show all
Defined in:
lib/ntm.rb,
lib/ntm/version.rb

Constant Summary collapse

DEFAULT_MAX_DEPTH = 
10
VERSION = 
"0.1.0"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}, &block) ⇒ Ntm

Returns a new instance of Ntm.



11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/ntm.rb', line 11

def initialize(options={}, &block)
  tape =  Tape.new(content: options[:tape_content], head_position: options[:head_position].to_i)
  @initial_state = options[:initial_state] || 0
  @initial_config = Configuration.new(state: @initial_state, tape: tape)
  #puts "initial state: #{initial_state}"
  @config_queue =  [@initial_config]
  @instructions =  {}
  @result_of_computation = []

  @input = nil

  instance_eval(&block) if block_given?
end

Instance Attribute Details

#instructions ⇒ Object (readonly)

attr_reader :current_state



9
10
11
 
# File 'lib/ntm.rb', line 9

def instructions
  @instructions
end

Instance Method Details

#add_instruction(given, transition) ⇒ Object

add a single instruction to the instructions set instructions must be in the following format:

given is a hash       {state:1, symbol: '0'}
transition is a hash  {state:2, symbol: '1', move: :right}



56
57
58
59
60
61
62
 
# File 'lib/ntm.rb', line 56

def add_instruction(given, transition)
  if instructions[given]
    instructions[given] << transition
  else
    instructions[given] = [transition]
  end
end

#given(options, &block) ⇒ Object

Raises:

  • (StandardError) 


34
35
36
37
38
39
40
 
# File 'lib/ntm.rb', line 34

def given(options, &block)
  raise StandardError, 'Missing input state of the transition function!' unless options[:state]
  raise StandardError, 'Missing input symbol of the transition function!' unless options[:symbol]

  @input = { state:options[:state], symbol: options[:symbol] }
  instance_eval(&block)
end

#instructions_count ⇒ Object 



65
66
67
68
69
 
# File 'lib/ntm.rb', line 65

def instructions_count
  count = 0
  instructions.each_value { |instrs| count += instrs.size }
  count
end

#reset ⇒ Object 



44
45
46
47
 
# File 'lib/ntm.rb', line 44

def reset
  @config_queue = [@initial_config]
  @result_of_computation = []
end

#run(options = {}) ⇒ Object

Raises:

  • (StandardError) 


72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/ntm.rb', line 72

def run(options = {})

  max_depth = options[:max_depth] || DEFAULT_MAX_DEPTH
  max_depth = max_depth.to_i
  accept_states = options[:accept_states] || []

  raise StandardError, 'Maximum depth must be a positive number!' unless max_depth > 0


  if  options[:tape_content] || options[:head_position]
    tape_content = options[:tape_content] || @initial_config.tape.content
    head_position = options[:head_position] || @initial_config.tape.head_position
    tape = Tape.new(content: tape_content, head_position: head_position.to_i)
    @config_queue =  [Configuration.new(state: @initial_state, tape: tape)]
  end

  loop do
    break if @config_queue.empty?

    config = deque_configuration

    if accept_states.include?(config.state)
      @result_of_computation << config.dup
      next
    end

    instrs = instructions[{state: config.state, symbol: config.tape.read}]
    if instrs == nil
      @result_of_computation << config.dup
      next
    end

    instrs.each do |instr|
      new_config = run_instruction(instr, config)
      # increase the depth
      new_config.depth = config.depth + 1
      # add the path
      new_config.path = config.path.dup << {instr:instr, config:config.to_s}
      #puts "#{new_config.depth} = #{new_config.to_s}"
      if new_config.depth >= max_depth
        @result_of_computation << new_config.dup
      else
        enque_configuration(new_config)
      end
    end
  end

  @result_of_computation.dup
end

#transition(options) ⇒ Object

Raises:

  • (StandardError) 


26
27
28
29
30
31
32
 
# File 'lib/ntm.rb', line 26

def transition(options)
  raise StandardError, 'Missing output state of the transition function!' unless options[:state]
  raise StandardError, 'Missing write-symbol of the transition function!' unless options[:symbol]
  raise StandardError, 'Missing head-move direction (right/left) of the transition function!' unless options[:move]

  add_instruction(@input, {state:options[:state], symbol:options[:symbol], move:options[:move]})
end