Understanding Computation (25 page)

It’s convenient to wrap all this up in a
DTM
class so we can have
#step
and
#run
methods, just like we did with the
small-step semantics implementation in
Chapter 2
:

class
DTM
<
Struct
.
new
(
:current_configuration
,
:accept_states
,
:rulebook
)
def
accepting?
accept_states
.
include?
(
current_configuration
.
state
)
end
def
step
self
.
current_configuration
=
rulebook
.
next_configuration
(
current_configuration
)
end
def
run
step
until
accepting?
end
end

We now have a working simulation of a deterministic Turing
machine, so let’s give it some input and try it out:

>>
dtm
=
DTM
.
new
(
TMConfiguration
.
new
(
1
,
tape
),
[
3
]
,
rulebook
)
=> #
>>
dtm
.
current_configuration
=> #>
>>
dtm
.
accepting?
=> false
>>
dtm
.
step
;
dtm
.
current_configuration
=> #>
>>
dtm
.
accepting?
=> false
>>
dtm
.
run
=> nil
>>
dtm
.
current_configuration
=> #>
>>
dtm
.
accepting?
=> true

As with our DPDA simulation, we need to do a bit more work to
gracefully handle a Turing machine becoming stuck:

>>
tape
=
Tape
.
new
(
[
'1'
,
'2'
,
'1'
]
,
'1'
,
[]
,
'_'
)
=> #
>>
dtm
=
DTM
.
new
(
TMConfiguration
.
new
(
1
,
tape
),
[
3
]
,
rulebook
)
=> #
>>
dtm
.
run
NoMethodError: undefined method `follow' for nil:NilClass

This time we don’t need a special representation of a stuck state.
Unlike a PDA, a Turing machine doesn’t have an external input, so we can
tell it’s stuck just by looking at its rulebook and current
configuration:

class
DTMRulebook
def
applies_to?
(
configuration
)
!
rule_for
(
configuration
)
.
nil?
end
end
class
DTM
def
stuck?
!
accepting?
&&
!
rulebook
.
applies_to?
(
current_configuration
)
end
def
run
step
until
accepting?
||
stuck?
end
end

Now the simulation will notice it’s stuck and stop
automatically:

>>
dtm
=
DTM
.
new
(
TMConfiguration
.
new
(
1
,
tape
),
[
3
]
,
rulebook
)
=> #
>>
dtm
.
run
=> nil
>>
dtm
.
current_configuration
=> #>
>>
dtm
.
accepting?
=> false
>>
dtm
.
stuck?
=> true

Just for fun, here’s the Turing machine we saw earlier, for recognizing strings like
'aaabbbccc'
:

>>
rulebook
=
DTMRulebook
.
new
(
[
# state 1: scan right looking for a
TMRule
.
new
(
1
,
'X'
,
1
,
'X'
,
:right
),
# skip X
TMRule
.
new
(
1
,
'a'
,
2
,
'X'
,
:right
),
# cross out a, go to state 2
TMRule
.
new
(
1
,
'_'
,
6
,
'_'
,
:left
),
# find blank, go to state 6 (accept)
# state 2: scan right looking for b
TMRule
.
new
(
2
,
'a'
,
2
,
'a'
,
:right
),
# skip a
TMRule
.
new
(
2
,
'X'
,
2
,
'X'
,
:right
),
# skip X
TMRule
.
new
(
2
,
'b'
,
3
,
'X'
,
:right
),
# cross out b, go to state 3
# state 3: scan right looking for c
TMRule
.
new
(
3
,
'b'
,
3
,
'b'
,
:right
),
# skip b
TMRule
.
new
(
3
,
'X'
,
3
,
'X'
,
:right
),
# skip X
TMRule
.
new
(
3
,
'c'
,
4
,
'X'
,
:right
),
# cross out c, go to state 4
# state 4: scan right looking for end of string
TMRule
.
new
(
4
,
'c'
,
4
,
'c'
,
:right
),
# skip c
TMRule
.
new
(
4
,
'_'
,
5
,
'_'
,
:left
),
# find blank, go to state 5
# state 5: scan left looking for beginning of string
TMRule
.
new
(
5
,
'a'
,
5
,
'a'
,
:left
),
# skip a
TMRule
.
new
(
5
,
'b'
,
5
,
'b'
,
:left
),
# skip b
TMRule
.
new
(
5
,
'c'
,
5
,
'c'
,
:left
),
# skip c
TMRule
.
new
(
5
,
'X'
,
5
,
'X'
,
:left
),
# skip X
TMRule
.
new
(
5
,
'_'
,
1
,
'_'
,
:right
)
# find blank, go to state 1
]
)
=> #
>>
tape
=
Tape
.
new
(
[]
,
'a'
,
[
'a'
,
'a'
,
'b'
,
'b'
,
'b'
,
'c'
,
'c'
,
'c'
]
,
'_'
)
=> #
>>
dtm
=
DTM
.
new
(
TMConfiguration
.
new
(
1
,
tape
),
[
6
]
,
rulebook
)
=> #
>>
10
.
times
{
dtm
.
step
};
dtm
.
current_configuration
=> #>
>>
25
.
times
{
dtm
.
step
};
dtm
.
current_configuration
=> #>
>>
dtm
.
run
;
dtm
.
current_configuration
=> #>

This implementation was pretty easy to build—it’s not hard to
simulate a Turing machine as long as we’ve got data structures to
represent tapes and rulebooks. Of course, Alan Turing specifically
intended them to be simple so they would be easy to build and to reason
about, and we’ll see later (in
General-Purpose Machines
) that this ease of implementation
is an important
property.