How can a cyclic tag system halt with an output?

Question

For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-computable function.

How can a cyclic tag system compute this (which it can, by definition of it being Turing-complete) when it only halts when it reaches the empty string? The Wikipedia article gives an example of converting to a 2-tag system, but it adds an emulated halt that the original system does not have.

I can't find any reference to how a cyclic tag system halts meaningfully. What is its output supposed to be? I've considered things like

• Number of steps (but then input restricts possible output without some kind of fancy encoding I can't find)
• The last production (but that only has a finite output range)
• Fixed points (which can't be detected in this system and only exist with very limited production rules and inputs)

but they don't work, at least not in any way I can see.

Answer 1

Neary and Woods describe an efficient simulation of Turing machines using cyclic tag systems, improving on work of Matthew Cook. Turing-completeness is a somewhat fluid and informal notion. A computing system X simulates another computing system Y if given each program in Y we can come up with a program in X such that looking at the transcript of the X-program, we can recover a transcript of the Y-program.

You can look at the papers above to see what this means for cyclic tag systems. The basic idea is that when the Turing machine halts, the cyclic tag systems keeps going, forever repeating the same sequence of configurations, representing the halting configuration of the Turing machine. In this sense it can actually compute functions.

---

In an earlier answer I noted that some computation models can only compute decision problems, in the sense that they either don't halt, or they halt with just one bit of output. In that case you can encode general function in at least two ways:

1. Given a function $f$, consider the language of pairs $\langle x,f(x) \rangle$.

2. Given a function $f$, consider the language of triples $\langle x,i,b \rangle$ such that the $i$th bit of $f(x)$ (if any) equals $b$.

As usual, we require that the machine always halt.

Answer 2

Although non-halting versions of cyclic tag may be of special interest for cellular automata, a cyclic tag system can also be designed to simulate a universal Turing machine in such a way that it halts iff the TM halts, displaying an output word that encodes the machine's output:

1. Simulate the TM with a 2-tag system that encodes all of the TM's instantaneous configurations, using a separate "output alphabet" to encode any halting configuration, such that the tag system halts (by erasing this word letter-by-letter) iff the TM halts. (This paper shows in detail how this can be done using a Wang machine formulation of TMs.)

2. Simulate the 2-tag system by a cyclic tag system as described in the Wikipedia article's cyclic tag system section. Since each letter in the 2-tag output alphabet has an empty string as its appendant (causing the 2-tag simulation to halt), the cyclic tag system will have the same halting/output behavior.

The key in this approach is that a designated output alphabet, say $\{\alpha_i\}$, allows each of its letters to have the empty string as its appendant ($\alpha_i\rightarrow \epsilon$), causing the simulation to erase the dataword and halt.

NB: For all three types of system (TM, tag, cyclic tag), the unambiguous identification of output can be ensured by using a specified output alphabet, and this can be done for both halting and non-halting varieties of these systems. (Given that "standard" TMs are of the halting kind, it is ironic that Turing's original computing machines were of the non-halting variety with output alphabet $\{0,1\}$.)

---

With the same approach, we can also directly construct a simple 2-tag system to erase any $0$s from a binary string, then simulate that with cyclic tag. The computations quickly get tedious, so we'll only apply it to the input string $101$, halting with the output string $11$. (The symbol - will denote the empty string.)

2-tag

input alphabet {a,b}, output alphabet {c}
input encoding:
<0> = aa
<1> = bb
input = <101> = bbaabb
output decoding: <cc> = 1

productions:

a -> - 
b -> cc 
c -> - 

computation:

bbaabb   <-- input word <101>
  aabbcc
    bbcc
      cccc  <-- output word <11>
        cc
         -

cyclic tag

encoding the 2-tag alphabet:

<a> = 100
<b> = 010
<c> = 001
cyclic tag system = [-,001001,-,-,-,-]
cyclic tag input = <bbaabb> = 010010100100010010 

computation:

appendant    dataword
---------    ---------------------------------------------------------------
-            010010100100010010  <-- input word <bbaabb> = <<101>>
001001        10010100100010010
-              0010100100010010001001
-               010100100010010001001
-                10100100010010001001
-                 0100100010010001001
-                  100100010010001001
001001              00100010010001001
-                    0100010010001001
-                     100010010001001
-                      00010010001001
-                       0010010001001
-                        010010001001
001001                    10010001001
-                          0010001001001001
-                           010001001001001
-                            10001001001001
-                             0001001001001
-                              001001001001  <-- output word <cccc> = <<11>>
001001                          01001001001
-                                1001001001
-                                 001001001
-                                  01001001
-                                   1001001
-                                    001001
001001                                01001
-                                      1001
-                                       001
-                                        01
-                                         1
-                                         -