How can a cyclic tag system halt with an output?
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:


Given a function $f$, consider the language of pairs $\langle x,f(x) \rangle$.
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.