1
$\begingroup$

Considering a 2-tag system as defined by wikipedia, how do I identify the result of the computation?

$\endgroup$
1
$\begingroup$

There are two types of Post tag systems: with halting symbols, and without.

A Post tag system with a halting symbol gives its output in the same way that a standard Turing machine does: on the tape. Whatever is written on the tape when it hits the halting symbol is its output.

A Post tag system without a halting symbol is a bit trickier. It only halts when the tape has too few symbols left to do another step of processing. So there's no way to give any output on the tape. Thus, its output is the sequence of intermediate states the system has been in in the process of producing the result.

The Wikipedia article you linked gives an example of this: a halting-symbol-less 2-tag system to compute the modified Collatz sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.