Class: Automata::Turing

Inherits:
StateDiagram show all
Defined in:
lib/automata/turing.rb

Overview

Turing Machine

Instance Attribute Summary collapse

Attributes inherited from StateDiagram

#accept, #alphabet, #start, #states, #transitions

Instance Method Summary collapse

Constructor Details

#initialize(params = {}) ⇒ Turing

TODO:

Check that each state is connected. Iterate through each states to verify the graph is not disjoint.

Returns a new instance of Turing.



10
11
12
13
14
15
16
17
18
19
 
# File 'lib/automata/turing.rb', line 10

def initialize(params={})
  yaml = {}
  yaml = YAML::load_file(params[:file]) if params.has_key? :file
  super(params)
  @inputAlphabet = params[:inputAlphabet] || yaml['inputAlphabet']
  @tapeAlphabet = params[:tapeAlphabet] || yaml['tapeAlphabet']
  @tape = Tape.new
  @accept = false
  @reject = false
end

Instance Attribute Details

#inputAlphabet ⇒ Object

Returns the value of attribute inputAlphabet.



4
5
6
 
# File 'lib/automata/turing.rb', line 4

def inputAlphabet
  @inputAlphabet
end

#reject ⇒ Object

Returns the value of attribute reject.



4
5
6
 
# File 'lib/automata/turing.rb', line 4

def reject
  @reject
end

#tape ⇒ Object

Returns the value of attribute tape.



4
5
6
 
# File 'lib/automata/turing.rb', line 4

def tape
  @tape
end

#tapeAlphabet ⇒ Object

Returns the value of attribute tapeAlphabet.



4
5
6
 
# File 'lib/automata/turing.rb', line 4

def tapeAlphabet
  @tapeAlphabet
end

Instance Method Details

#accepts?(input) ⇒ Boolean

Determines whether the TM halts in an accept state.

Parameters:

  • input (String) —

    the string to use as input for the TM.

Returns:

  • (Boolean) —

    Whether or not the TM accepts the input string.



61
62
63
64
 
# File 'lib/automata/turing.rb', line 61

def accepts?(input)
  resp = feed(input)
  resp[:accept]
end

#feed(input) ⇒ Hash

Runs the input on the turing machine and returns a Hash describing the machine’s final state after running.

Parameters:

  • input (String) —

    the string to use as input/tape for the TM

Returns:

  • (Hash) —

    a hash describing the TM state after running

    • :input [String] the original input string

    • :accept [Boolean] whether or not the TM halted in an accept state

    • :reject [Boolean] whether or not the TM halted in a reject state

    • :head [String] the state which the head halted

    • :tape [String] the resulting tape string



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/automata/turing.rb', line 31

def feed(input) 
  @tape = Tape.new(input)
  @accept = false
  @reject = false

  stateHead = @start.to_s
  input.each_char do |symbol|
    toState = transition(stateHead, symbol)
    if @accept || @reject
      break
    else
      stateHead = toState
    end
  end
  
  resp = {
    input: input,
    accept: @accept,
    reject: @reject,
    head: stateHead,
    tape: @tape.memory,
    output: @tape.output
  }
  resp
end

#has_transition?(state, read) ⇒ Boolean

Determines whether or not any transition states exist given a beginning state and input symbol pair.

Parameters:

  • state (String) —

    state label for beginning state.

  • symbol (String) —

    input symbol.

Returns:

  • (Boolean) —

    Whether or not a transition exists.



99
100
101
102
 
# File 'lib/automata/turing.rb', line 99

def has_transition?(state, read)
  return false unless @transitions.include? state
  @transitions[state].has_key? read
end

#rejects?(input) ⇒ Boolean

Determines whether the TM halts in an reject state.

Parameters:

  • input (String) —

    the string to use as input for the TM.

Returns:

  • (Boolean) —

    Whether or not the TM rejects the input string.



70
71
72
73
 
# File 'lib/automata/turing.rb', line 70

def rejects?(input)
  resp = feed(input)
  resp[:reject]
end

#transition(state, symbol) ⇒ Array

Note:

Turing machines have two unique states:

  • ACCEPT Unique accept state

  • REJECT Unique reject state

Determines the transition states, if any, from a given beginning state and input symbol pair.

Parameters:

  • state (String) —

    state label for beginning state.

  • symbol (String) —

    input symbol.

Returns:

  • (Array) —

    Array of destination transition states.



84
85
86
87
88
89
90
91
92
 
# File 'lib/automata/turing.rb', line 84

def transition(state, symbol)
  actions = @transitions[state][symbol]
  @tape.transition(symbol, actions['write'], actions['move'])

  # Flip the bits for halting states
  @accept = true if actions['to'] == 'ACCEPT'
  @reject = true if actions['to'] == 'REJECT'
  @head = actions['to']
end