Post tag systems
The Post tag machine is simple to the point of triviality. The system is a queue of characters (with one character designated as "Halt"), and a set of rules. Each rule has a different character that selects the rule, and a string of characters. Each step, the machine looks at the first character of the queue, and selects the rule associated with that character. If the character is "Halt", the system just stops, and whatever is left on the queue is the result of the computation. Otherwise, it appends the selected rule's string of characters to the end of the queue, and then removes a fixed number of characters from the front of the queue. The systems are called N-Tag systems where N is number of character dropped each step.
That's it. Look at the front of the queue, use it to pick a set of characters to append, and then remove and discard the first N characters from the queue.
For any N>=2, a Post N-tag system is Turing equivalent.
The Tag language
Tag is an implementation of a Post-tag system with a variable drop length: each rule specifies how many characters should be removed from the queue when that rule is selected.
The syntax is very simple: It's a list of rules. Each rule has the format:
name ":" triggerchar numbertodrop "("characters to append")"
addThreeAsOnB:B2(AAA) is a rule named
addThreeAsOnB. It will run when the first character on the queue is
B, and it will drop the first two characters from the queue, and append
For output, if the number to drop is followed by
!, then it will print out the dropped characters except for the one that triggered the command.
The classic Hello World program:
fillQueue:a2(pHpeplplpop pWpoprplpd#) printChar:p2!(#)
ifA:A2(sss) ifB:B2(ss) ifS:s2(cd) ifC:c2(pA#) ifD:d2(pB#) print:p2!( )
What this does is: if the first character is an
A, it inserts 3
ss; if it's
B, it inserts two
ss. On an
s, it appends
c causes it to print
A and then halt;
d causes it to print
B and halt.
So suppose we started with
AA on the queue. It would pick the rule
ifA:, drop the two
As, and the queue would be
sss. Then it would pick rule
s, which drops two, and appends
cd - so the queue would be
scd. It would run
s again, which would append another
pB#, so the queue becomes
pB#pA#. And then
B gets printed, and the program halts.
Let's look at the other cases:
BB on the queue. Rule
B runs, leaving
ss on the queue.
cd on the queue. The
pA# onto the queue, leaving the queue as
pA#. So it prints
A, and halts.
Takes a list of digits terminated with an 'x', and outputs the sum of the digits in Unary format:
zero :01() one :11(p1) two :21(p1p1) three:31(p1p1p1) four :41(p1p1p1p1) five :51(p1p1p1p1p1) six :61(p1p1p1p1p1p1) seven:71(p1p1p1p1p1p1p1) eight:81(p1p1p1p1p1p1p1p1) nine :91(p1p1p1p1p1p1p1p1p1) end :x1(#) print:p2!()
An initial queue of
52341x would produce the output
Takes a digit (followed by !) and outputs the factorial, in unary.
one :12(p1) two :22(p1p1) three:32(2 2 2 ) four :42(3 3 3 3 ) five :52(4 4 4 4 4 ) six :62(5 5 5 5 5 5 ) seven:72(6 6 6 6 6 6 6 ) eight:82(7 7 7 7 7 7 7 7 ) nine :92(8 8 8 8 8 8 8 8 8 ) print:p2!(#)'