Echo Tag
Echo Tag is an esoteric programming language created by User:ais523 in 2018, in an attempt to find a cyclic tag variant that's even simpler to implement. (The perceived issues with cyclic tag that make can sometimes make it hard to implement in low-level languages are that programs effectively have three instructions (e.g. 0, 10, 11 in Bitwise Cyclic Tag) rather than two, and that the queue and program don't move at a constant rate relative to each other, requiring additional control flow.)
Specification
Echo Tag is a restricted subset of cyclic tag, with the following restrictions:
- Every production consists only of a single character (i.e. either each production is made entirely of 0s, or each production is made entirely of 1s). (This restriction is just a simplification, as it's always possible to work around by recoding a digit in the data queue as multiple equal digits.)
- Every production has the same length.
A program is thus uniquely defined by the (shared) length of the productions (called n), the initial data queue, and the first character of each production, which is the form used to write an Echo Tag program.
Expanding this definition, an Echo Tag program is formed by a number n, a list of "productions" (which are single bits, 0 or 1), and a data queue (a queue made out of 0 bits and 1 bits). Execution of the program is done by repeatedly following the following steps:
- Delete the head bit of the data queue. (If the data queue is empty, the program terminates.)
- Move the first production in the list to the end.
- If the deleted bit was a 1 bit, then append n copies of the production that was moved to the end of the data queue.
- Go back to step 1. (The steps repeat forever, or until the program terminates due to an empty data queue.)
Computational class
Echo Tag is Turing-complete if arbitrarily large n are allowed, because tag systems can be compiled into it. Because the "every production consists only of a single character" rule of Echo Tag is trivially worked around (via replacing every digit with n copies of itself and splitting each of the resulting rules into n pieces), all that's necessary to prove is that any tag system can be compiled into a cyclic tag system for which every production has the same length.
To accomplish this, we first form a sequence of tag system symbols Q (of length q) that has all the productions of the tag system as (ordered, but not necessarily contiguous) subsequences. (This can be achieved simply by concatenating all the productions, although sharing bits between them is likely to be more efficient). Let p be the number of productions in the tag system (i.e. the number of distinct symbols it has), and m be the stride length of the tag system. Each tag system symbol is given an arbitrary number j from 0 to p-1 inclusive. We take n as pm+q.
The tag system's symbols in its data queue are encoded into the Echo Tag data queue in one of two ways:
- Encoding A
- Each tag system symbol j is encoded as n bits in the Echo Tag queue. Numbering the bits from 0 at the leftmost end to (n-1) at the rightmost end, bits numbered from jm inclusive to (j+1)m exclusive are 1 bits; all the others are 0 bits.
- Encoding B
- Each tag system symbol j is encoded as mn bits in the Echo Tag queue: n(m-1)+pm 0 bits, followed by q bits that select the system's production from Q (i.e. if you take the symbols from Q that are in the same position as the 1 bits in those q bits, in the same order, you get the production for symbol j; you can always find such a sequence because Q has every production of the tag system as a subsequence). This encoding allows "comments", in the form of mn consecutive 0 bits, to be inserted anywhere; an encoding containing a comment has the same meaning as the encoding without the comment.
Initially, the Echo Tag data string is an Encoding A encoding of the tag system data string.
The Echo Tag productions are derived from the tag system productions as follows:
- 1 copy of:
- for each of the p tag system symbols (in numerical order), a (comment-less) Encoding B encoding of that symbol, split into m chunks of n bits (thus pm chunks of n bits in total), followed by
- Q, encoded using Encoding A (this consists of q productions, each encoded as n bits);
- then, (m-1) copies of:
- pm productions that each consist of n 0 bits, followed by
- Q, encoded using Encoding A (this consists of q productions, each encoded as n bits).
In total, the system thus has (m-1)(pm+q) + 1(pm+q) = mn productions of n bits each.
Executing the Echo Tag system will basically simulate the tag system while continuously switching back and forth between Encoding A and Encoding B:
- Initially, the data string is in Encoding A, and it can be seen that this implements the way that tag systems ignore all but the leftmost in every block of m symbols: there are mn productions, and each symbol is encoded as n bits, so the Echo Tag productions repeat every m tag system symbols, re-encoding all the symbols that matter in Encoding B and all the symbols that will be deleted as Encoding B comments. Notably, after the entire Encoding A portion of the string has been processed, the position of the Echo Tag productions will record the length of the tag system string so far mod m. Because Encoding B encodings are multiples of mn bits wide (whether or not comments are inserted), this position will be retained while processing an Encoding B string, so when the tag system goes back to processing Encoding A data, it will "start up where it left off" and not lose the information about which symbols need to be deleted.
- Once an initial Encoding A string has been processed, the entire data string will be in Encoding B (with comments added). It can be seen that a comment, mn consecutive 0 bits, will have no effect on the state of the Echo Tag system (other than deleting itself); it'll just cause all the mn productions to cycle round once uselessly and end back where they started. As such, the resulting string is the same as it would be if all the non-comment Encoding B symbols were processed. Because a 1 bit in an Encoding B encoding must be in the last q bits of the encoding, and every block of n productions in the Echo Tag system has the same final q bits, it does not matter for this processing where the Echo Tag system is relative to its full cycle of mn productions (as long as it starts at the start of a block of n bits, which it always does because all symbols in all encodings have widths that are a multiple of n); in any case, an Encoding B symbol j will cause the relevant encodings from Q to be selected, and end up writing the tag system's jth production to the Echo Tag system's data string in Encoding A.
The Echo Tag system thus simulates the tag system in a mildly asynchronous way; instead of strictly interleaving production lookups followed by deletions, a block of deletions are calculated first, and the production lookups later. Nonetheless, it comes to the same result, so the Echo Tag system simulates the steps of the tag system. In particular, when the data string returns to Encoding A, the Echo Tag system's data string has a length exactly n times that of the tag system, meaning that when the tag system's data string is empty, so will the Echo Tag system's be. This means that they halt at the same time, so as long as arbitrarily large n are allowed, Echo Tag is Turing-complete.
More interesting, though, is what happens with small n. The minimum Turing-complete value for n is believed to be 2 (although this has not been formally proved yet): see the discussion at The Program Is Mostly Ignored. (Obviously, it must be greater than 1, or else there's no way for the data queue to ever expand.) The minimum n that has been proven Turing-complete is 68, using the construction above on UT19 (which gives p=19, m=2, q=30 for [18, 1, 1, 2, 3, 4, 4, 5, 6, 5, 7, 8, 9, 11, 10, 10, 12, 12, 12, 12, 13, 14, 14, 14, 14, 15, 16, 16, 17, 19], thus n=pm+q=19×2+30=68); any higher n must also be Turing-complete because it is possible to add useless symbols to Q in order to increase q without otherwise changing the construction.