Acyclic Tag
Acyclic Tag is an esoteric programming language created by User:ais523 in 2019. It's heavily inspired by cyclic tag, but aims to be even simpler to implement: compiling Acyclic Tag to cyclic tag is easy, but the other direction is much more difficult. This means in turn that Acyclic Tag can be used to prove more languages Turing-complete than cyclic tag can.
Specification
An Acyclic Tag program consists of a table and an initial queue. The table never changes during the duration of the program; the queue's initial value is set by the program, but the queue itself changes as the program executes. The state of an executing program also contains a pointer into the table; initially, it points to the first table element.
The table and queue both contain commands; the queue is a queue of commands, and the table is an array of strings of commands. Four commands exist, each of which has its own effect when executed:
| Command | Effect when executed |
|---|---|
+ |
Moves the pointer to point at the next table element. Undefined behaviour if this moves it outside the table. |
- |
Moves the pointer to point at the previous table element. Undefined behaviour if this moves it outside the table. |
^ |
Pushes a copy of each command in the pointed-to table element onto the queue, in order. |
.number |
Outputs the character with codepoint number to standard output. (The number is written in decimal.) |
Program execution proceeds by repeatedly shifting a command off the queue, and then executing it, producing one of the above effects. If the queue is ever discovered to be empty when attempting to shift a command off the queue, the program halts.
When storing programs in a file, the file consists of each element of the table, separated by newlines, followed by a newline and the initial string. A trailing newline is permitted; this must be given if the initial string is empty (to avoid ambiguity), and is otherwise optional; other than that, the only vertical whitespace allowed is the newlines that separate table elements from each other and from the initial string. Horizontal whitespace is allowed anywhere between commands. There is no comment syntax.
Relationship to cyclic tag
Just like Acyclic Tag, it is possible to think about cyclic tag as a table of strings of commands (the productions), a pointer (the current production), and a queue of commands (the data string). In cyclic tag, the 0 command increases the pointer (wrapping from end to start), and the 1 command pushes a copy of the pointed-to production onto the queue, then increases the pointer (again wrapping from end to start). Thus, 0 corresponds to Acyclic Tag's +, and 1 to ^+.
Although Acyclic Tag's - does not directly have an equivalent command, it's easy to synthesize one by using 0 a number of times equal to the number of productions minus 1, making use of the wrapping behaviour. ^ can then be implemented as 1-. Thus, an Acyclic Tag program without I/O can be compiled directly into cyclic tag (+ as 0, - as 0…0, ^ as 10…0).
Compilation in the other direction is much more difficult, though: cyclic tag programs typically depend strongly on the wrapping behaviour from the end to the start of the table of productions, whereas this does not exist in Acyclic Tag (thus the name "acyclic"); Acyclic Tag can be thought of as a language in which the wrapping of the pointer from one end of the table has to be done manually, rather than being done automatically by the language semantics. This makes Acyclic Tag more difficult to program in, but consequently, easier to implement.
Example
Here's an Acyclic Tag program that outputs the Fibonacci sequence in unary (by acting as a neighbour-independent substitution system):
+^-^ ^.49 .10++^-- ^++^--
and a debug trace of the program running (showing the output on the left, then the pointer, currently executing command, and queue):
0|^|++^--
0|+|+^--+^-^
1|+|^--+^-^
2|^|--+^-^
2|-|-+^-^.10++^--
1|-|+^-^.10++^--
0|+|^-^.10++^--
1|^|-^.10++^--
1|-|^.10++^--^.49
0|^|.10++^--^.49
0|.|++^--^.49+^-^
0|+|+^--^.49+^-^
1|+|^--^.49+^-^
2|^|--^.49+^-^
2|-|-^.49+^-^.10++^--
1|-|^.49+^-^.10++^--
0|^|.49+^-^.10++^--
0|.|+^-^.10++^--+^-^
1 0|+|^-^.10++^--+^-^
1|^|-^.10++^--+^-^
1|-|^.10++^--+^-^^.49
0|^|.10++^--+^-^^.49
0|.|++^--+^-^^.49+^-^
0|+|+^--+^-^^.49+^-^
1|+|^--+^-^^.49+^-^
2|^|--+^-^^.49+^-^
2|-|-+^-^^.49+^-^.10++^--
1|-|+^-^^.49+^-^.10++^--
0|+|^-^^.49+^-^.10++^--
1|^|-^^.49+^-^.10++^--
1|-|^^.49+^-^.10++^--^.49
0|^|^.49+^-^.10++^--^.49
0|^|.49+^-^.10++^--^.49+^-^
0|.|+^-^.10++^--^.49+^-^+^-^
1 0|+|^-^.10++^--^.49+^-^+^-^
1|^|-^.10++^--^.49+^-^+^-^
1|-|^.10++^--^.49+^-^+^-^^.49
0|^|.10++^--^.49+^-^+^-^^.49
0|.|++^--^.49+^-^+^-^^.49+^-^
0|+|+^--^.49+^-^+^-^^.49+^-^
1|+|^--^.49+^-^+^-^^.49+^-^
2|^|--^.49+^-^+^-^^.49+^-^
2|-|-^.49+^-^+^-^^.49+^-^.10++^--
1|-|^.49+^-^+^-^^.49+^-^.10++^--
0|^|.49+^-^+^-^^.49+^-^.10++^--
0|.|+^-^+^-^^.49+^-^.10++^--+^-^
1 0|+|^-^+^-^^.49+^-^.10++^--+^-^
1|^|-^+^-^^.49+^-^.10++^--+^-^
1|-|^+^-^^.49+^-^.10++^--+^-^^.49
0|^|+^-^^.49+^-^.10++^--+^-^^.49
0|+|^-^^.49+^-^.10++^--+^-^^.49+^-^
1|^|-^^.49+^-^.10++^--+^-^^.49+^-^
1|-|^^.49+^-^.10++^--+^-^^.49+^-^^.49
0|^|^.49+^-^.10++^--+^-^^.49+^-^^.49
0|^|.49+^-^.10++^--+^-^^.49+^-^^.49+^-^
0|.|+^-^.10++^--+^-^^.49+^-^^.49+^-^+^-^
1 0|+|^-^.10++^--+^-^^.49+^-^^.49+^-^+^-^
1|^|-^.10++^--+^-^^.49+^-^^.49+^-^+^-^
1|-|^.10++^--+^-^^.49+^-^^.49+^-^+^-^^.49
0|^|.10++^--+^-^^.49+^-^^.49+^-^+^-^^.49
0|.|++^--+^-^^.49+^-^^.49+^-^+^-^^.49+^-^
Quine
This quine uses value 10 for newline.
++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++^------++++++++^--------^+++++++^-------+^-++++++^------++^--++++++++^--------+++++^-----^+^-++++^----^+++++++^-------+^-^+^-+++^---++++++^------++^--++^--++++++++^--------+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++^--++++++++^--------+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----+++++^-----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+^-++++^----^+++++++^-------+^-^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---^+^-+++^---++++++^------^+^-+++++++++++^-----------++++++^------^+++^---++++++++++++^------------++++++^------^+^-++++^----++++++^------^+++^---++++^----++++++^------^+++^---++++++++++^----------++++++^------^+^-+++^---++++++^------^++++++++++^----------+++++++++^---------++++++^------^+++^---+++++++++++++^-------------++++++^------^+++++++^-------+^-++++++^------^+^-++++++++++++++^--------------++++++^------^+^-+++++++^-------++++++^------^+++^---+^-++++++^------^+++^---+++++++++^---------++++++^------^+++^---+++^---++++++^------^+++^---+++++++++++^-----------++++++^------++++++++^--------++^--+++++++++++++++ ^.94 +^-.43.94.45 ++^--.43.43.94.45.45 +++^---.43.43.43.94.45.45.45 ++++^----.43.43.43.43.94.45.45.45.45 +++++^-----.43.43.43.43.43.94.45.45.45.45.45 ++++++^------.43.43.43.43.43.43.94.45.45.45.45.45.45 +++++++^-------.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45 ++++++++^--------.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45 +++++++++^---------.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45 ++++++++++^----------.43.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45.45 +++++++++++^-----------.43.43.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45.45.45 ++++++++++++^------------.43.43.43.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45.45.45.45 +++++++++++++^-------------.43.43.43.43.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45.45.45.45.45 ++++++++++++++^--------------.43.43.43.43.43.43.43.43.43.43.43.43.43.43.94.45.45.45.45.45.45.45.45.45.45.45.45.45.45 .46 .52 .43 .53 .51 .45 .10 .57 .94 .48 .49 .54 .50 .55 .56 ^+
Acyclic Tag Assembler
Acyclic Tag Assembler is a notation designed to make it easier to write and understand large Acyclic Tag programs. It compiles more or less directly into Acyclic Tag.
Acyclic Tag Assembler refers to the various table entries of an Acyclic Tag program as combinations of a number and a set of letters, representing an index within the table via a sort of place-value system comparable to Roman Numerals. The numbers range from 0 to some value n, and are the least significant part of the table index; then A represents 20(n+1), B represents 21(n+1), C represents 22(n+1) and so on. Thus, if n=9, 0 would refer to the entry with index 0 (the first entry), 4A to the entry with index 14, 7BC to the entry with index 67, and so on.
An Acyclic Tag Assembler program starts with n on a line by itself, followed by the highest-valued letter used, in lowercase, on a line by itself. This is then followed by descriptions of table entries, each on their own line, and finally the initial string.
A table entry description consists of a pattern and a string. The pattern consists of a number, followed by zero or more letters in uppercase or lowercase. A pattern can match multiple indexes within the table: if a letter is not present, the pattern matches the index with and without that letter; if a letter is present in uppercase, the pattern matches the index only with that letter; if a letter is present in lowercase, the pattern matches the index only without that letter. Thus, if the highest-valued letter used is b, 5 would match 5, 5A, 5B, and 5AB, whereas 5aB would match only 5B.
For strings (either the initial string, or the string side of a pattern), a number x (that is not part of a .x command) represents x + commands, then a ^ command, then x - commands. An uppercase letter represents the matching amount of + commands. A lowercase letter represents the matching amount of - commands. (Assemblers are permitted and encouraged to optimise out any +- and -+ sequences that result from these expansions.)
If more than one pattern matches a table index, the most specific description is used (the one which contains the most letters in the pattern), or the first in the program if there's still a tie. If no pattern matches a table index, the default is to assume that the appropriate expansion is to copy the number portion of the index (thus if no pattern matched 2C, the assumed replacement would be 2, i.e. ++^--).
To make it easy to implement halting programs, an uppercase letter just after the "highest-valued letter" may be present in a string, in which case all table entries that contain that letter will be left blank. (As long as the letter is only executed once, executing it will cause all future ^ commands to do nothing, due to pointing to empty table elements, and thus inevitably cause the program to eventually halt.)
Here's an example Acyclic Tag Assembler program:
5 a 0A 2A 1A a3 4A 4 2A 0 a3 0 2A 1 a3 0 2A 0 a3 1 2A 1 a3 4 2A 0 a3 0 2A 1 a3 1 2A 0 a3 1 2A 1 a3
and an Acyclic Tag program it could assemble to:
^ +^- ++^-- +++^--- ++++^---- +++++^----- ++^++++ ---^--- ++^-- +++^--- ++++^---- +++++^----- ++^++++ ^ ---^--- ^ ++^++++ +^- ---^--- ^ ++^++++ ^ ---^--- +^- ++^++++ +^- ---^--- ++++^---- ++^++++ ^ ---^--- ^ ++^++++ +^- ---^--- +^- ++^++++ ^ ---^--- +^- ++^++++ +^- ---^---
Computational class
Acyclic Tag is Turing-complete. However, just as with An Odd Rewriting System, the known proofs of this lead to inefficient programs; it is not known whether or not it is possible to avoid an exponential slowdown when implementing some Turing machines.
The Acyclic Tag Assembler example above shows a basic building block that can be useful in Turing-completeness proofs. Here are the names of the table entries which are pushed onto the queue as it runs:
2 0A 3 0 2 1A 3 0 2 0A 3 1 2 1A 3 4 2 0A 3 0 2 1A 3 1 2 0A 3 1 2 1A 3 2 2 3A 0A 2A 3 3 0 2 2 3A 1A 2A 3 3 4 2 2 3A 0A 2A 3 3 1 2 2 3A 1A 2A 3 3 2 2 3 2 2A 3A 3A 0A 2A 2A 3A 3 2 3 3 4 2 2 3 2 2A 3A 3A 1A 2A 2A 3A 3 2 3 3 2 2 3 2 2 3 3 2 2A 2A 3A 3A 2A 3A 3A 4A 2A 2A 3A 2A 2A 3A 3A 3 2 2 3 3 2 3 3 2 2 3 2 2 3 3 2 2 2 3 3 2 3 3 4 2 2 3 2 2 3 3 3 2 2 3 3 2 3 3 2 2 3 2 2 3 3 2 2 2 3 3 2 3 3 4 2 2 3 2 2 3 3 3 2 2 3 3 2 3 3 (the pattern continues forever)
The basic idea is that 0…1 brackets are used to mark parts of the queue that can become Active; their expansions are unbalanced, causing all the ^ commands between them to index the A versions of the commands in question. After being activated, 0 and 1 become 2 and 3 respectively, and pay no further part on the execution of the system. (A more complex program would have a mechanism to reset them back to their starting states so that the block of code could be reused, which is the reason that they don't just outright delete themselves.) The result creates a tree of recursive "escaping" that pushes the 4A entry after a given delay (the delay could be lengthened by making the tree larger).
It is fairly straightforward to generate this sort of recursive-escaping pattern from within an Acyclic Tag program (because you can generate it from a 1-tag system, thus don't need to worry about maintaining state from one element to the next). The next stage is to use multiple such patterns, plus a generator for this sort of pattern, to effectively create an expanding tape for which only one element is ever active at a time; the only real difficulty here is in telling the generator when to stop expanding the pattern and commit it to the tape. This can be accomplished via, e.g., having all the active tape elements (the equivalent of 4A in the above) decrement the pointer by, e.g., the amount represented as B, and have the generator itself increase the pointer by that much; as long as the existing tape is still running these adjustments will cancel each other out, but when the existing portion of the tape is exhausted, the generator's increase will happen with nothing to cancel it. After a while, this ends up producing the C version of every table entry (with two unbalanced Bs applied; a single B is not sufficient evidence of tape exhaustion, because the extra B is not added and removed in the same place); this version can be designed reset the tape elements (and the trees that activate them), and put everything back to normal. The result is a steadily-growing tape whose elements are examined in order, one at a time, and which get an opportunity to undo any unbalanced changes to the pointer they've made before the next active tape element runs.
From this point, demonstrating Turing-completeness is fairly easy. A compiler from Consistent 01-2C to Acyclic Tag Assembler is available as an explicit construction proving Turing-completeness. (This construction uses the same general principles as in the discussion above, but uses a more optimised numbering of table entries.)
See also
External resources
- Acyclic Tag implementation in Perl (fairly slow, but with a range of debugging features)
- Assembler from Acyclic Tag Assembler to Acyclic Tag
- Compiler from Consistent 01-2C to Acyclic Tag Assembler