Understanding Computation (44 page)

The fact that tag systems can simulate any Turing machine means that
they too are
universal.

A
cyclic tag system
is a
tag system that has been made even simpler by imposing some
extra constraints:

By themselves, these constraints are too severe to support any kind of useful computation,
so cyclic tag systems get an extra feature to compensate: the first rule in a cyclic tag
system’s rulebook is the
current rule
when execution begins, and after
each step of computation, the next rule in the rulebook becomes current, wrapping back to the
first rule when the end of the rulebook is reached.

This kind of system is called “cyclic” because of the way the current rule cycles
repeatedly through the
rulebook. The use of a current rule, combined with the constraint that every rule
applies to strings beginning with
1
, avoids the overhead of
having to search through the rulebook to find an applicable rule at each step of execution; if
the first character’s a
1
, then the current rule applies,
otherwise, no rule does.

As an example, let’s look at the cyclic tag system with three rules
that append the characters
1
,
0010
, and
10
,
respectively. Here’s what happens when it’s started with the string
11
:

Despite the extreme simplicity of this system, we can see a hint of complex behavior: it’s
not obvious what will happen next. With a bit of thought we can convince ourselves that the
system will run forever rather than dwindle to the empty string, because every rule appends a
1
, so as long as the initial string contains a
1
, it will never die out entirely.
^[
61
]
But will the current string keep fitfully growing longer, or will it settle into a
repeating pattern of expansion and contraction? Just looking at the rules doesn’t answer that
question; we need to keep running the system to find out what happens.

We already have a Ruby implementation of a conventional tag system, so simulating a cyclic
tag system doesn’t require much extra work. We can implement a
Cyclic
TagRule
simply by subclassing
TagRule
and hardcoding
'1'
as its
first_character
:

class
CyclicTagRule
<
TagRule
FIRST_CHARACTER
=
'1'
def
initialize
(
append_characters
)
super
(
FIRST_CHARACTER
,
append_characters
)
end
def
inspect
"##{
append_characters
.
inspect
}
>"
end
end

The rulebook for a cyclic tag system works slightly differently, so
we’ll build a
CyclicTagRulebook
class
from scratch, providing new implementations of
#applies_to?
and
#next_string
:

class
CyclicTagRulebook
<
Struct
.
new
(
:rules
)
DELETION_NUMBER
=
1
def
initialize
(
rules
)
super
(
rules
.
cycle
)
end
def
applies_to?
(
string
)
string
.
length
>=
DELETION_NUMBER
end
def
next_string
(
string
)
follow_next_rule
(
string
)
.
slice
(
DELETION_NUMBER
.
.
-
1
)
end
def
follow_next_rule
(
string
)
rule
=
rules
.
next
if
rule
.
applies_to?
(
string
)
rule
.
follow
(
string
)
else
string
end
end
end

Unlike a vanilla
TagRulebook
, a
CyclicTagRulebook
always applies to any nonempty string, even if
the current rule doesn’t.

>>
numbers
=
[
1
,
2
,
3
].
cycle
=> #
>>
numbers
.
next
=> 1
>>
numbers
.
next
=> 2
>>
numbers
.
next
=> 3
>>
numbers
.
next
=> 1
>>
[
:a
,
:b
,
:c
,
:d
].
cycle
.
take
(
10
)
=> [:a, :b, :c, :d, :a, :b, :c, :d, :a, :b]

Now we can create a
CyclicTagRulebook
full of
CyclicTagRule
s and plug it into a
TagSystem
to see it working:

>>
rulebook
=
CyclicTagRulebook
.
new
(
[
CyclicTagRule
.
new
(
'1'
),
CyclicTagRule
.
new
(
'0010'
),
CyclicTagRule
.
new
(
'10'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'11'
,
rulebook
)
=> #
>>
16
.
times
do
puts
system
.
current_string
system
.
step
end
;
puts
system
.
current_string
11
11
10010
001010
01010
1010
01010
1010
0100010
100010
000101
00101
0101
101
010010
10010
00101
=> nil

That’s the same behavior we saw when we stepped through the
execution by hand. Let’s keep going:

>>
20
.
times
do
puts
system
.
current_string
system
.
step
end
;
puts
system
.
current_string
00101
0101
101
011
11
110
101
010010
10010
00101
0101
101
011
11
110
101
010010
10010
00101
0101
101
=> nil

So it turns out that this system
does
settle
down into repetitive behavior when it’s started with the string
11
: after an initial period of instability, a
pattern of nine consecutive strings emerges (
101
,
010010
,
10010
,
00101
, …) and repeats itself forever. Of course,
if we change the initial string or any of the rules, the long-term
behavior will be different.

Cyclic tag systems are extremely limited—they have inflexible rules, only two characters,
and the lowest possible deletion number—but surprisingly, it’s still possible to use them to
simulate
any
tag system.

The simulation of a normal tag system by a cyclic tag system works
like this: