PkmnQ⁧⁦ is cool⁩⁦

PkmnQ⁧⁦ is cool⁩⁦ 1 year ago (edited) • 3 views

And there, finished that post. It's done now in case anyone wants to read it in depth.

PkmnQ⁧⁦ is cool⁩⁦ 1 year ago (edited) • 6 views

you know what who cares anymore i'm going tagposting

Tag systems are a very simple system of computation that works as follows:
During runtime, a string of symbols are kept. Depending on what the first symbol is, a different production is appended to the end, then the first m symbols are removed. If the string is empty, it halts. There are slight differences in this definition depending on what's convenient, but the main idea of appending and removing stays the same.
m=2 is known to be Turing-complete and is, as far as I know, the most oftenly used value of m. If you inspect any m=2 tag system, you'll notice that not only is data stored in the symbols themselves, but also in the even/odd-ness of their positions. For example, take this Collatz example:

a -> bc
b -> a
c -> aaa

Let's run this with the starting string being aaaaa. (the --'s are just for spacing)

aaaaa
--aaabc
----abcbc
------cbcbc
--------cbcaaa
----------caaaaaa
------------aaaaaaaa

Because the amount of a's was odd, it skipped over the b, and only ran the c's. Now let's continue.

aaaaaaaa
--aaaaaabc
----aaaabcbc
------aabcbcbc
--------bcbcbcbc
----------bcbcbca
------------bcbcaa
--------------bcaaa
----------------aaaa

Since it was even this time, the b's ran and skipped over the c's. "bc" acts as a single unit that does different things depending on the parity of the a's.
It also helps to think of tag systems in terms of generations, starting with the initial string (e.g. aaaaa) to the string generated by the initial string (e.g. cbcbc) to the string generated by that (e.g. aaaaaaaa) etc. A better example for this kind of thing is UT19, which is split into three separate generations forming a single cycle. The specifics of what UT19 accomplishes will not be noted here.
As an example, here are two "inverters", which are used to flip the parity from even to odd and odd to even during the Command generation:

Relevant productions:
a -> bc
b -> dd
c -> rd
d -> aas
r -> r
s -> (nothing)

aasaas (Command generation)
--saasbc
----asbc
------bcbc (Parity generation)
--------bcdd
----------dddd (Reset generation)
------------ddaas
--------------aasaas (Command generation)

More complicated parts of UT19 change every cycle, such as the counters. They can either double or halve their length each generation:

Relevant productions:
a -> bc
b -> dd
c -> rd
d -> aas
l -> nnnn
m -> o
n -> pp
o -> pq
p -> lm
q -> llll
r -> r
s -> (nothing)

lmlm (Command generation)
--lmnnnn
----nnnnnnnn (Parity generation)
------nnnnnnpp
--------nnnnpppp
----------nnpppppp
------------pppppppp (Reset generation)
--------------pppppplm
----------------pppplmlm
------------------pplmlmlm
--------------------lmlmlmlm (Command generation)

(The parity each generation is entered is important, so two inverters are used)
aaslmlmaas (Command)
--slmlmaasbc
----mlmaasbc
------maasbco
--------asbcoo
----------bcoobc (Parity)
------------oobcdd
--------------bcddpq
----------------ddpqdd (Reset)
------------------pqddaas
--------------------ddaaslm
----------------------aaslmaas (Command)

(In case you're wondering about the reason for the q symbol or what happens when you halve lm, those are involved with a more complicated component, and are the reason behind the name of the "Reset" generation.)

This will only be the first in a series of posts, with the next one covering Cyclic tag.

0

0

There are no comments here yet!