Sequential tag system
A sequential tag system is similar to a cyclic tag system, but where the production rules are given as an explicit, infinitely long list, rather than as a finitely long list that repeats.
Sequential tag systems are often the simplest way to prove a language Turing complete – if it accepts an infinitely long input program, as is the case for many cellular automata and some Turing machines. This definition of Turing-completeness is quite controversial, due to the introduction of infinity. However, because a cyclic tag program compiles into a sequential tag program that repeats indefinitely, then in many cases, this will lead to an infinitely repeating program in the language whose computational class is being examined, something that most (but not all) mathematicians will accept as a legitimate initialization.
Here are some implementations of sequential tag system:
- This article is a stub, which means that it is not detailed enough and needs to be expanded. Please help us by .