Echo Tag

From Esolang
Jump to: navigation, search

Echo Tag is an esoteric programming language created by User:ais523 in Category: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:

  1. Delete the head bit of the data queue. (If the data queue is empty, the program terminates.)
  2. Move the first production in the list to the end.
  3. 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.
  4. Go back to step 1. (The steps repeat forever, or until the program terminates due to an empty data queue.)

Computational class

ais523's attempted Turing-completeness proof of Echo Tag was flawed (and potentially uninteresting because n was very large), although it's highly likely to be fixable. More interesting, though, is what happens with small n: ais523 conjectures that the minimum Turing-complete value of n is probably either 2 or 3, possibly 4. (Obviously, it must be greater than 1, or else there's no way for the data queue to ever expand.) Anyone have any ideas for proving this Turing complete with small n?

See also