Understanding Computation (45 page)

Let’s make those ideas more concrete by implementing them. First we
need to be able to ask a tag system what characters it uses:

class
TagRule
def
alphabet
(
[
first_character
]
+
append_characters
.
chars
.
entries
)
.
uniq
end
end
class
TagRulebook
def
alphabet
rules
.
flat_map
(
&
:alphabet
)
.
uniq
end
end
class
TagSystem
def
alphabet
(
rulebook
.
alphabet
+
current_string
.
chars
.
entries
)
.
uniq
.
sort
end
end

We can test this on the number-incrementing tag system from
Tag Systems
.
TagSystem#alphabet
tells us that this system
uses the characters
a
,
b
,
c
, and
d
:

>>
rulebook
=
TagRulebook
.
new
(
2
,
[
TagRule
.
new
(
'a'
,
'ccdd'
),
TagRule
.
new
(
'b'
,
'dd'
)
]
)
=> #
>>
system
=
TagSystem
.
new
(
'aabbbb'
,
rulebook
)
=> #
>>
system
.
alphabet
=> ["a", "b", "c", "d"]

Next we need a way of encoding each character as a string that the
cyclic tag system can use. There’s a specific encoding scheme that makes
the simulation work: each character is represented as a string of
0
s with the same length as the alphabet, with a
single
1
character in a position that
reflects that character’s position in the alphabet.
^[
62
]

Our tag system has a four-character alphabet, so each letter gets
encoded as a four-character string with a
1
in a different place:

To implement this encoding scheme, we’ll introduce a
CyclicTagEncoder
that gets constructed with a specific alphabet and then asked to
encode strings of characters from that alphabet:

class
CyclicTagEncoder
<
Struct
.
new
(
:alphabet
)
def
encode_string
(
string
)
string
.
chars
.
map
{
|
character
|
encode_character
(
character
)
}
.
join
end
def
encode_character
(
character
)
character_position
=
alphabet
.
index
(
character
)
(
0
.
.
.
alphabet
.
length
)
.
map
{
|
n
|
n
==
character_position
?
'1'
:
'0'
}
.
join
end
end
class
TagSystem
def
encoder
CyclicTagEncoder
.
new
(
alphabet
)
end
end

Now we can use our tag system’s
CyclicTagEncoder
to encode any strings made up
of
a
,
b
,
c
, and
d
:

>>
encoder
=
system
.
encoder
=> #
>>
encoder
.
encode_character
(
'c'
)
=> "0010"
>>
encoder
.
encode_string
(
'cab'
)
=> "001010000100"

The encoder gives us a way to convert each tag system rule into a
cyclic tag system rule. We just encode the
append_characters
of a
TagRule
and use the resulting string to build a
CyclicTagRule
:

class
TagRule
def
to_cyclic
(
encoder
)
CyclicTagRule
.
new
(
encoder
.
encode_string
(
append_characters
))
end
end

Let’s try that on a single
TagRule
:

>>
rule
=
system
.
rulebook
.
rules
.
first
=> #
>>
rule
.
to_cyclic
(
encoder
)
=> #

Alright, so the
append_characters
have been converted,
but now we’ve lost the information about which
first_character
is supposed to trigger the rule—every
Cyclic
TagRule
is triggered by the character
1
regardless of which
TagRule
it was converted from.

Instead, that information is communicated by the
order
of the rules in the cyclic tag system: the
first rule is for the first character in the alphabet, the second rule is
for the second character, and so on. Any character without a corresponding
rule in the tag system gets a blank rule in the cyclic tag system
rulebook.

We can implement a
TagRulebook#cyclic_rules
method to return the
converted rules in the right order:

class
TagRulebook
def
cyclic_rules
(
encoder
)
encoder
.
alphabet
.
map
{
|
character
|
cyclic_rule_for
(
character
,
encoder
)
}
end
def
cyclic_rule_for
(
character
,
encoder
)
rule
=
rule_for
(
character
)
if
rule
.
nil?
CyclicTagRule
.
new
(
''
)
else
rule
.
to_cyclic
(
encoder
)
end
end
end

Here’s what
#cyclic_rules
produces for our tag system:

>>
system
.
rulebook
.
cyclic_rules
(
encoder
)
=> [
#,
#,
#,
#
]

As expected, the converted
a
and
b
rules appear first, followed by two
blank rules in the
c
and
d
positions.

This arrangement dovetails with the character encoding scheme to
make the whole simulation work. If the simulated tag system’s input string
is the single character
b
, for
instance, it will appear as
0100
in the
input string of the cyclic tag system. Watch what happens when the system
runs with that input:

On the first step of computation, the converted
a
rule
is current, and doesn’t get used because the current string begins with a
0
. But on the second step, the
b
rule becomes current just as the leading
0
is deleted from the current string, revealing a leading
1
that triggers the rule. The next two characters are both
0
,
so the
c
and
d
rules
don’t get used either.

So, by carefully timing the appearances of the character
1
in the input string to coincide with the
rotating appearances of rules in the cyclic tag system, we can trigger the
right rules at the right times, perfectly simulating the
character-matching behavior of conventional tag system rules.

Finally, we need to simulate the deletion number of the original tag system, but that’s
easily done by inserting extra empty rules into the cyclic tag system’s rulebook so that the
right number of characters get deleted after a single encoded character has been successfully
processed. If the original tag system has
n
characters in its alphabet,
then each character of the original system’s string is represented as
n
characters in the cyclic tag system’s string, so we need
n
blank rules for
every additional simulated character that we want to delete:

class
TagRulebook
def
cyclic_padding_rules
(
encoder
)
Array
.
new
(
encoder
.
alphabet
.
length
,
CyclicTagRule
.
new
(
''
))
*
(
deletion_number
-
1
)
end
end

Our tag system has a four-character alphabet and a deletion number
of 2, so we need an extra four empty rules to delete one simulated
character in addition to the one that already gets deleted by the
converted rules:

>>
system
.
rulebook
.
cyclic_padding_rules
(
encoder
)
=> [
#,
#,
#,
#
]