Understanding Computation (24 page)

For a particular
Turing machine design to be deterministic, it has to obey the same constraints
as a deterministic pushdown automaton (see
Determinism
), although
this time we don’t have to worry about free moves, because Turing machines don’t have
them.

A Turing machine’s next action is chosen according to its current state and the
character currently underneath its tape head, so a deterministic machine can only have one
rule for each combination of state and character—the “no contradictions” rule—in order to
prevent any ambiguity over what its next action will be. For simplicity, we’ll relax the “no
omissions” rule, just as we did for DPDAs, and assume there’s an implicit stuck state that
the machine can go into when no rule applies, instead of insisting that it must have a rule
for every possible situation.

Now that we have a good idea of how a deterministic Turing machine
should work, let’s build a Ruby simulation of one so we can see it in
action.

The first step is to implement a Turing machine tape. This
implementation obviously has to store the characters that are written on
the tape, but it also needs to remember the current position of the tape
head so that the simulated machine can read the current character, write
a new character at the current position, and move the head left and
right to reach other positions.

An elegant way of doing this is to split up the tape into three
separate parts—all the characters to the left of the tape head, the
single character directly underneath it, and all the characters to its
right—and store each part separately. This makes it very easy to read
and write the current character, and moving the tape head can be
achieved by shuffling characters between all three parts; moving one
square to the right, for instance, means that the current character
becomes the last character to the left of the head, and the first
character to the right of the head becomes the current one.

Our implementation must also maintain the illusion that the tape is infinitely long and
filled with blank squares, but fortunately, we don’t need an infinitely large data structure
to do this. The only tape location that can be read at any given moment is the one that’s
beneath the head, so we just need to arrange for a new blank character to appear there
whenever the head is moved beyond the finite number of nonblank characters already written
on the tape. To make this work, we need to know in advance which character represents a
blank square, and then we can make that character automatically appear underneath the tape
head whenever it moves into an unexplored part of the tape.

So, the basic representation of a tape looks like this:

class
Tape
<
Struct
.
new
(
:left
,
:middle
,
:right
,
:blank
)
def
inspect
"##{
left
.
join
}
(
#{
middle
}
)
#{
right
.
join
}
>"
end
end

This lets us create a tape and read the character beneath the tape
head:

>>
tape
=
Tape
.
new
(
[
'1'
,
'0'
,
'1'
]
,
'1'
,
[]
,
'_'
)
=> #
>>
tape
.
middle
=> "1"

We can add operations to write to the current tape
position
^[
37
]
and move the head left and right:

class
Tape
def
write
(
character
)
Tape
.
new
(
left
,
character
,
right
,
blank
)
end
def
move_head_left
Tape
.
new
(
left
[
0
.
.
-
2
]
,
left
.
last
||
blank
,
[
middle
]
+
right
,
blank
)
end
def
move_head_right
Tape
.
new
(
left
+
[
middle
]
,
right
.
first
||
blank
,
right
.
drop
(
1
),
blank
)
end
end

Now we can write onto the tape and move the head around:

>>
tape
=> #
>>
tape
.
move_head_left
=> #
>>
tape
.
write
(
'0'
)
=> #
>>
tape
.
move_head_right
=> #
>>
tape
.
move_head_right
.
write
(
'0'
)
=> #

In
Chapter 4
, we used the word
configuration
to refer to the combination of a pushdown
automaton’s state and stack, and the same idea is useful here. We can say that a
Turing machine configuration
is the combination of a state and a
tape, and implement Turing machine rules that deal directly with those
configurations:

class
TMConfiguration
<
Struct
.
new
(
:state
,
:tape
)
end
class
TMRule
<
Struct
.
new
(
:state
,
:character
,
:next_state
,
:write_character
,
:direction
)
def
applies_to?
(
configuration
)
state
==
configuration
.
state
&&
character
==
configuration
.
tape
.
middle
end
end

A rule only applies when the machine’s current state and the
character currently underneath the tape head match its
expectations:

>>
rule
=
TMRule
.
new
(
1
,
'0'
,
2
,
'1'
,
:right
)
=> #state=1,
character="0",
next_state=2,
write_character="1",
direction=:right
>
>>
rule
.
applies_to?
(
TMConfiguration
.
new
(
1
,
Tape
.
new
(
[]
,
'0'
,
[]
,
'_'
)))
=> true
>>
rule
.
applies_to?
(
TMConfiguration
.
new
(
1
,
Tape
.
new
(
[]
,
'1'
,
[]
,
'_'
)))
=> false
>>
rule
.
applies_to?
(
TMConfiguration
.
new
(
2
,
Tape
.
new
(
[]
,
'0'
,
[]
,
'_'
)))
=> false

Once we know that a rule applies to a particular configuration, we
need the ability to update that configuration by writing a new
character, moving the tape head, and changing the machine’s state in
accordance with the rule:

class
TMRule
def
follow
(
configuration
)
TMConfiguration
.
new
(
next_state
,
next_tape
(
configuration
))
end
def
next_tape
(
configuration
)
written_tape
=
configuration
.
tape
.
write
(
write_character
)
case
direction
when
:left
written_tape
.
move_head_left
when
:right
written_tape
.
move_head_right
end
end
end

That code seems to work fine:

>>
rule
.
follow
(
TMConfiguration
.
new
(
1
,
Tape
.
new
(
[]
,
'0'
,
[]
,
'_'
)))
=> #>

The
implementation of
DTMRulebook
is almost the
same as
DFARulebook
and
DPDARulebook
, except
#next_configuration
doesn’t take a
character
argument, because there’s no
external input to read characters from (only the tape, which is already part of the
configuration):

class
DTMRulebook
<
Struct
.
new
(
:rules
)
def
next_configuration
(
configuration
)
rule_for
(
configuration
)
.
follow
(
configuration
)
end
def
rule_for
(
configuration
)
rules
.
detect
{
|
rule
|
rule
.
applies_to?
(
configuration
)
}
end
end

Now we can make a
DTMRulebook
for the “increment a binary number” Turing machine and use it to
manually step through a few configurations:

>>
rulebook
=
DTMRulebook
.
new
(
[
TMRule
.
new
(
1
,
'0'
,
2
,
'1'
,
:right
),
TMRule
.
new
(
1
,
'1'
,
1
,
'0'
,
:left
),
TMRule
.
new
(
1
,
'_'
,
2
,
'1'
,
:right
),
TMRule
.
new
(
2
,
'0'
,
2
,
'0'
,
:right
),
TMRule
.
new
(
2
,
'1'
,
2
,
'1'
,
:right
),
TMRule
.
new
(
2
,
'_'
,
3
,
'_'
,
:left
)
]
)
=> #
>>
configuration
=
TMConfiguration
.
new
(
1
,
tape
)
=> #>
>>
configuration
=
rulebook
.
next_configuration
(
configuration
)
=> #>
>>
configuration
=
rulebook
.
next_configuration
(
configuration
)
=> #>
>>
configuration
=
rulebook
.
next_configuration
(
configuration
)
=> #>