Understanding Computation (41 page)

A
tag system
is a model
of computation that works like a simplified Turing machine: instead of moving a
head back and forth over a tape, a tag system operates on a string by repeatedly adding new
characters to the end of the string and removing them from the beginning. In some ways, a tag
system’s string is like a Turing machine’s tape, but the tag system is constrained to only
operate on the edges of the string, and it only ever “moves” in one direction—toward the
end.

A tag system’s description has two parts: first, a collection of
rules, where each rule specifies some characters to append to the string
when a particular character appears at the beginning—“when the character
a
is at the beginning of the string,
append the characters
bcd
,” for
instance; and second, a number, called the
deletion
number
, which specifies how many characters to delete from the
beginning of the string after a rule has been followed.

Here’s an example tag system:

We can perform a tag system computation by repeatedly following rules and deleting
characters until the first character of the string has no applicable rule, or until the length
of the string is less than the deletion number.
^[
58
]
Let’s try running the example tag system with the initial string
'aaaaaa'
:

Tag systems only operate directly on strings, but we can get them to
perform sophisticated operations on other kinds of values, like numbers,
as long as we have a suitable way to encode those values as strings. One
possible way of encoding numbers is this: represent the number
n
as the string
aa
followed by
n
repetitions of the string
bb
; for example, the number 3 is represented as
the string
aabbbbbb
.

Once we’ve chosen an encoding scheme for numbers, we can design tag
systems that perform operations on numbers by manipulating their string
representations. Here’s a system that doubles its input number:

Watch how this tag system behaves when started with the string
aabbbb
, representing the number
2:

aabbbb → bbbbaa
→ bbaabbbb
→ aabbbbbbbb
(representing the number 4)
→ bbbbbbbbaa
→ bbbbbbaabbbb
→ bbbbaabbbbbbbb
→ bbaabbbbbbbbbbbb
→ aabbbbbbbbbbbbbbbb
(the number 8)
→ bbbbbbbbbbbbbbbbaa
→ bbbbbbbbbbbbbbaabbbb
⋮

The doubling is clearly happening, but this tag system runs
forever—doubling the number represented by its current string, then
doubling it again, then again—which isn’t really what we had in mind. To
design a system that doubles a number just once and then halts, we need to
use different characters to encode the result so that it doesn’t trigger
another round of doubling. We can do this by relaxing our encoding scheme
to allow
c
and
d
characters in place of
a
and
b
, and
then modifying the rules to append
cc
and
dddd
instead of
aa
and
bbbb
when creating the representation of the doubled number.

With those changes, the computation looks like this:

aabbbb → bbbbcc
→ bbccdddd
→ ccdddddddd
(the number 4, encoded with
c
and
d
instead of
a
and
b
)

The modified system stops when it reaches
ccdddddddd
,
because there’s no rule for strings beginning with
c
.

To simulate a tag system in Ruby, we need an implementation of an
individual rule (
TagRule
), a collection
of rules (
TagRulebook
), and the tag
system itself (
TagSystem
):

class
TagRule
<
Struct
.
new
(
:first_character
,
:append_characters
)
def
applies_to?
(
string
)
string
.
chars
.
first
==
first_character
end
def
follow
(
string
)
string
+
append_characters
end
end
class
TagRulebook
<
Struct
.
new
(
:deletion_number
,
:rules
)
def
next_string
(
string
)
rule_for
(
string
)
.
follow
(
string
)
.
slice
(
deletion_number
.
.
-
1
)
end
def
rule_for
(
string
)
rules
.
detect
{
|
r
|
r
.
applies_to?
(
string
)
}
end
end
class
TagSystem
<
Struct
.
new
(
:current_string
,
:rulebook
)
def
step
self
.
current_string
=
rulebook
.
next_string
(
current_string
)
end
end

This implementation allows us to step through a tag system
computation one rule at a time. Let’s try that for the original doubling
example, this time getting it to double the number 3 (
aabbbbbb
):

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'aa'
),
TagRule
.
new
(
'b'
,
'bbbb'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbbbb'
,
rulebook
)
=> #
>>
4
.
times
do
puts
system
.
current_string
system
.
step
end
;
puts
system
.
current_string
aabbbbbb
bbbbbbaa
bbbbaabbbb
bbaabbbbbbbb
aabbbbbbbbbbbb
=> nil

Because this tag system runs forever, we have to know in advance how many steps to execute
before the result appears—four steps, in this case—but if we used the modified version that
encodes its result with
c
and
d
, we could just let it run until it stops automatically. Let’s add the code to
support that:

class
TagRulebook
def
applies_to?
(
string
)
!
rule_for
(
string
)
.
nil?
&&
string
.
length
>=
deletion_number
end
end
class
TagSystem
def
run
while
rulebook
.
applies_to?
(
current_string
)
puts
current_string
step
end
puts
current_string
end
end

Now we can just call
TagSystem#run
on the halting version of the tag
system and let it naturally stop at the right point:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'cc'
),
TagRule
.
new
(
'b'
,
'dddd'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbbbb'
,
rulebook
)
=> #
>>
system
.
run
aabbbbbb
bbbbbbcc
bbbbccdddd
bbccdddddddd
ccdddddddddddd
=> nil