[Solved]: How can a cyclic tag system halt with an output?

Problem Detail: 

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.

Asked By : Fricative Melon

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44226

3.2K people like this

 Download Related Notes/Documents