Understanding Computation (42 page)

This implementation of tag systems allows us to explore what else they’re capable of. With
our encoding scheme, it’s easy to design systems that perform other numeric operations, like
this one for halving a number:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'cc'
),
TagRule
.
new
(
'b'
,
'd'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbbbbbbbbbb'
,
rulebook
)
=> #
>>
system
.
run
aabbbbbbbbbbbb
bbbbbbbbbbbbcc
bbbbbbbbbbccd
bbbbbbbbccdd
bbbbbbccddd
bbbbccdddd
bbccddddd
ccdddddd
=> nil

And this one, which increments a number:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'ccdd'
),
TagRule
.
new
(
'b'
,
'dd'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbb'
,
rulebook
)
=> #
>>
system
.
run
aabbbb
bbbbccdd
bbccdddd
ccdddddd
=> nil

We can also join two tag systems together, as long as the output
encoding of the first system matches the input encoding of the second.
Here’s a single system that combines the doubling and incrementing rules
by using the characters
c
and
d
to encode the input to the incrementing rules
and
e
and
f
to encode their output:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'cc'
),
TagRule
.
new
(
'b'
,
'dddd'
),
# double
TagRule
.
new
(
'c'
,
'eeff'
),
TagRule
.
new
(
'd'
,
'ff'
)
# increment
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbb'
,
rulebook
)
=> #
>>
system
.
run
aabbbb
(the number 2)
bbbbcc
bbccdddd
ccdddddddd
(the number 4)
ddddddddeeff
ddddddeeffff
ddddeeffffff
ddeeffffffff
eeffffffffff
(the number 5)
=> nil

As well as changing numbers into other numbers, tag systems can
check their mathematical properties. Here’s a tag system that tests
whether a number is odd or even:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'cc'
),
TagRule
.
new
(
'b'
,
'd'
),
TagRule
.
new
(
'c'
,
'eo'
),
TagRule
.
new
(
'd'
,
''
),
TagRule
.
new
(
'e'
,
'e'
)
]
)
=> #

If its input represents an even number, this system stops at the
single-character string
e
(which stands
for “even”):

>>
system
=
TagSystem
.
new
(
'aabbbbbbbb'
,
rulebook
)
=> #
>>
system
.
run
aabbbbbbbb
(the number 4)
bbbbbbbbcc
bbbbbbccd
bbbbccdd
bbccddd
ccdddd
ddddeo
ddeo
eo
e
=> nil