UT19
UT19 is a specific 2-tag system that was developed by User:ais523 in 2023. It was created to be a universal tag system (i.e. it implements a Turing-complete language) with a fairly small number of symbols, each of which has a fairly simple definition, making it a possible tool to use for Turing-completeness proofs of languages (sometimes a language can be shown to be able to emulate tag systems up to a certain complexity).
Another way to view UT19 is as the outcome of a code golfing experiment into how simple a universal tag system can be.
The production rules of UT19
UT19 has 19 symbols, named after the integers from 1 to 19 inclusive. The rules were originally written (and are written here) in JSON form, as an array of the 19 assigned words in numerical order of the symbol they are assigned to:
[[ 2, 3], [ 4, 4], [18, 4], [ 1, 1,19], [ 7, 9], [ 8, 9], [10,10], [11,10], [18,10], [ 5, 6], [ 6, 5,19], [14,14,14,14], [15], [16,16], [16,17], [12,13], [12,12,12,12], [18], []]
There are four different ways to handle halting in tag systems:
- they can be defined to halt if they attempt to expand a halt symbol;
- or to halt if the length of the queue becomes less than the parameter m (2 in the case of UT19);
- or if the queue becomes entirely empty, which has two possible variants with respect to what to do when the queue has fewer than m elements:
- either the queue positions continue to alternate between produced-from and deleted, so that if a single-symbol queue is produced from, the first symbol in the resulting production lands in a deleted spot and gets deleted rather than produced from;
- or, if fewer than m symbols remain in the queue, all of them are deleted, and the next symbol to be added is produced from.
UT19 is designed to be Turing-complete under the first three of these rules for when to halt; when a halt symbol is in use, the halt symbol is symbol 18. It can trivially be modified to be Turing-complete under the fourth rule too, by changing the production for symbol 18 from [18] to [18, 19, 19] (this change clearly does not affect the behaviour of the tag system in most cases, because [19, 19] is a no-op that produces nothing and does not affect the alternation of the queue; the change is helpful when using the fourth halting rule because it means that the final symbol that gets stuck in the queue will be a 19 rather than an 18, which is able to delete itself and end the program).
Computational class
UT19 is Turing complete because it can implement Brainpocalypse II. To prove this, this article will consider various parts of the program in turn.
The global cycle
The symbols of UT19 are divided into four groups: three "main groups" named Command, Parity, Reset, and two special symbols (18 and 19) that are not part of any of the groups. UT19 is designed around a "global cycle" in which each main group of symbols can create only symbols in the next main group (and special symbols): Command symbols produce only Parity and special symbols, Parity symbols produce only Reset and special symbols, and Reset symbols produce only Command and special symbols. Program execution can be divided into "cycles" as follows: the first cycle is the processing of the symbols of the initial string; the second cycle is the processing of the symbols that were produced during the first cycle; the third cycle is the processing of symbols that were produced during the second cycle; and so on. Each cycle thus contains only symbols from one of the three main groups. Due to the way that queues work, the symbols examined within each cycle will be in the same relative order as the symbols that produced them on the previous cycle; thus, e.g., the first symbol to be processed in a cycle will have been produced by the first non-19 symbol that was produced from in the previous cycle ("non-19" because 19 has an empty production).
A cycle can be either "odd" or "even". Treating the first symbol processed in a cycle as being index 0, the second as being index 1, the third as being index 2, and so on, an "even cycle" is one on which the even-indexed symbols are produced from, and the odd-indexed symbols are deleted and ignored; an "odd cycle" is the opposite, where the odd-indexed symbols are used and the even-indexed symbols are ignored. The oddness of various cycles is used to spread various information globally throughout the program:
- Oddness at the start of a Command cycle happens only immediately after a reset, i.e. when rewinding back to the start of the program due to an attempt to decrement 0; this happens if and only if the previous, Reset, cycle was also odd. This oddness is not used to convey information globally, and the initial condition is designed to compensate for it (as will be explained below).
- Oddness at the start of a Parity cycle occurs only when emulating a halt in the Brainpocalpyse II program, and never happens during normal program execution.
- Oddness at the start of a Reset cycle occurs if a reset is required, i.e. an attempt was made to decrement 0. Except during emulation of a halt, every production that runs on Parity (and thus produces symbols for Reset) has an even length; this means that the oddness/evenness of the cycle will be preserved throughout the entire cycle, with the symbols in even positions handling normal behaviour and the symbols in odd positions handling a reset. (Because every symbol on a Reset cycle has even length, the parity of a Reset cycle will be preserved into Command, explaining why it is odd only immediately after a reset.)
Just as with cycles as a whole, a substring of symbols can also be in an even or odd position. It makes sense to think of the "odd production" and "even production" of a string of symbols: the string that it will produce if run starting from an odd index, and if run starting from an even index. For example, when generating strings for Reset, Parity will generate strings whose odd production emulates a reset and whose even production emulates the next step in a Brainpocalpyse II program that was not reset. This means that it is meaningful to talk about the meaning conveyed by oddness of a string within a cycle (which could happen because the cycle is odd, xor because the string is preceded by an odd number of odd-length strings and thus is at an odd position within the cycle):
Oddness within a Command cycle is used for two purposes. For parts of the string that represent the Brainpocalypse II program, it is used in a fairly complicated way to advance from one command of the program to the next (specifically, it is used to track whether there are an odd or even number of running-XOR memory cells in state 1 before that point: see #Program memory below). For parts of the string that represent the Brainpocalypse II counters, it is used to specify what operation is being performed on that counter that cycle: counters in even positions increment, whereas counters in odd positions decrement. (It is impossible for a counter to stay the same on any given cycle, which is worked around by doubling all the counter values and subtracting 1: an increment is implemented as two increments, a decrement as two decrements, and "no change" as a decrement then an increment. This makes the implementation of decrement-from-0 a little more complicated than it otherwise would be, but only having to deal with two commands rather than three makes things much simpler, so it's worth it.)
Oddness within a Parity cycle has two possible meanings. The primary use of this oddness is to detect whether a counter has been decremented from 0; almost all productions generated by Command for Parity have even width, with the only exception being "decrementing counter". Counters are represented in an exponential format – on Parity, a counter that just decremented from value x is represented as 2x 15s – and thus the only string that will have odd length would be a counter that just decremented from 0. The counters alternate between all being even and all being odd every three cycles, so only on every sixth cycle is it possible for any counter to become zero, and on such cycles, the program is designed in such a way that one counter is ever decremented at a time; this means that only one part of the string, the counter being decremented, has any opportunity to have an odd width, with everything else having an even width. As such, the width of the Parity cycle as a whole will be odd if the decremented counter (if any) decremented from zero, and even in all other cases; this controls the parity at the start of Reset, which in turn emulates the rule of Brainpocalypse II that everything other than the counter values resets if any attempt is made to decrement a counter from zero. As such, oddness within Parity means "a counter somewhere before this position was decremented from zero", a fact which is generally ignored until the end of the cycle because it generally doesn't matter whether the zeroing counter is before or after the current location.
The second purpose of oddness within a Parity cycle is to serve as a global halt signal. In normal (non-halting) operation, any production from a symbol at an odd position in Parity will see oddness (all productions generated for a Reset cycle will arrive at an even position relative to the start of the cycle, because all productions that generate symbols for a Reset cycle have even length, but the cycle itself will be odd because only one thing in Parity is supposed to be odd, and thus the oddness will necessarily last until the start of Reset). Halting is thus emulated using symbols that are generated from an odd position in Parity but are at an even position within their productions, and thus only run if the Reset cycle is an even cycle. The halt state is intentionally set up by using a "halt counter", at the end of the list of counters, which always has the value 0 except when halting; the halt signal is sent using a Command cycle which contains an odd number of symbols (thus creating an odd Parity cycle) and that also decrements the halt counter from 0 (thus causing the Parity cycle to also contain an odd number of cycles, causing an even Reset cycle immediately after the odd Parity cycle). Everything in the program prior to the halt counter will be aware that a halt is occurring, and everything but counters in that location will collapse into a string of 18s (the halt symbol).
Oddness within a Reset cycle happens if and only if the Reset cycle itself is odd, because all productions produced by Parity for Reset have an even width.
Inverters
With this construction, the queue of a running UT19 will consist of a number of components. These are sections of symbols that (except during halt situations) recreate themselves, or (if they need to be stateful) something of the same nature but recording a state change, three cycles later. Another way to think about it is that each component has a "Command version", a "Parity version", and a "Reset version", which each create the other in sequence (thus the Command version produces the Parity version, which produces the Reset version, which produces the Command version again). Components can thus exist in the initial string and stay throughout program execution, in the same relative order.
The simplest component used in UT19 is the inverter, implemented using symbols 1, 2, 3 and 4. Inverters do not store long-term state (having a memory of only one cycle), and have an odd width during Command and an even width during Parity (and everything has an even width during Reset).
During Command, an inverter always takes the form [1, 1, 19]. (19 is a special symbol with an empty production; its purpose is to be added to the end of a production to cause it to have an odd width, without changing what is actually produced. In this case, it is being used to make the inverter length 3, which is odd, rather than the normal length 2.)
Regardless of whether the inverter was in an odd or even position during Command, it takes the form [2, 3] during Parity (generated by a 1 during Command). If the inverter is at an even position within Parity, the 2 will run, generating [4, 4] for Reset. If the inverter is at an odd position within Parity, the 3 will run, generating [18, 4] for Reset.
In most cases, the symbol that is produced from during Reset will be a 4, which generates [1, 1, 19] for Command, restoring the original form of the component. If the inverter was in an even position within Parity, it will have the form [4, 4] during Reset, thus producing from one of the 4s unconditionally (there is no reason to react to whether the program is being reset or not, as inverters do not have long-term memory and thus there is nothing to reset). If the inverter was in an odd position within Parity, this will in normal situations mean that everything will be in an odd position during Reset; its [18, 4] will thus again produce from a 4. The only situation in which the 18 is produced from is if the inverter was in an odd position within Parity, but even within Reset, the halt signal. As such, when using 18 as a halt symbol, any inverter in the program will cause the program to halt once the halt signal is received.
Program memory
What is being implemented
UT19 makes use of a number of "program memories" in order to remember both the Brainpocalypse II program itself, and the location of the Brainpocalypse II instruction pointer; these are not stored separately, but rather, each program memory has a fixed sequence of oddnesses and evennesses that it automatically moves forwards through every Command cycle, resetting back to the start of the sequence on every odd Reset cycle. (There are multiple program memories in order to be able to give different commands to different counters, with program memories existing before, after and between the counters.) Each program memory is a running-XOR memory.
The general idea of a running-XOR memory is that it is made out of an ordered array of cells, each either 0 or 1. On each cycle on which the running-XOR memory operates (which in the UT19 implementation, is each Command cycle), a cell will change value if it has an odd number of 1 cells before it. A running-XOR memory has an output, which is 1/odd if it contains an odd number of cells in state 1 and 0/even if it contains an even number of cells in state 1. Running-XOR memories of width 2n (for any nonnegative integer n) have a few interesting properties.
One of these is that flipping the state of the last 2x cells of a running-XOR memory will have an effect on its output only on every operating cycle that occurs at time -1 mod 2x relative to the time of the flip (e.g. for memory of size 8, if you flip the state of all cells on operative cycle 0, this will affect the output only on operating cycles 7, 15, 23, etc.), and the effect of the change will be to flip the output on and only on the affected cycles. This can be proved by induction on x. The base case, x=0, says that if the last cell of a running-XOR memory is flipped, this will flip its output on every operating cycle (which is obvious because this flip does not affect any other cell of the memory, and XOR is an associative operation so it is purely additive with the flips being made by earlier cells). For the recursive case, the effect of flipping the last 2x+1 cells of a running-XOR memory can be determined by splitting it into two 2x-cell blocks. The flip of everything will cause no change to the output of either for 2x-1 operating cycles. On the 2xth, both will have their output changed – but that won't change the output from the combined block, because changing the parity of both halves means that the parity of the combined block doesn't change. Additionally, the change in the parity before the later block will flip that block back to its original state. By the inductive hypothesis, another 2x-1 operating cycles happen with no change from the original (the earlier block is still flipped but the inductive hypothesis is that that doesn't matter for 2x-1 cycles, and the later block is now in its original configuration), and then on the 2x+1th operating cycle, there is now a change, when the earlier block has its output flipped but the later block has its original output. That causes the later block to flip back to its flipped state, and the pattern repeats.
This observation leads to a second observation: for any list of 2n outputs, there is some running-XOR memory of 2n cells that produces that sequence of outputs on the first 2n operating cycles, and will do so regardless of whether the entire state of the memory is flipped on any of those cycles. It is possible to determine the appropriate state for such a memory simply by starting with a memory of all-zeroes, then simulating 2n operating cycles of it, flipping the entire state of the memory before any operating cycle that corresponds to a cycle where you want a 1 output (and leaving it alone on cycles where you want a 0 output). There are more efficient algorithms to calculate the initial state, but the correctness of this one is an immediate consequence of the previous observation.
How it is being implemented
UT19 implements cells of UT19 memory using symbols 5 to 11 inclusive.
The implementation of a running-XOR memory in UT19 is as follows: during Command, each cell has an even width in state 0 and an odd width in state 1, and will change state if placed at an odd position within Command (i.e. if it has an odd number of 1 cells to its left); during Parity, it has an even width; and during Reset, it will reset to state 0 if placed at an odd position (and, of course, has an even width). Although there is no direct implementation of a cell that resets to state 1, it can be implemented using a cell that resets to state 0 with an inverter placed immediately after it (which comes to the same thing). This means that, by using running-XOR memory cells and inverters, it is possible to create a section of the tag system queue which will follow a desired pattern of odd/even widths on every Command cycle, resetting to the start of the sequence whenever an odd Reset cycle occurs. There is a slight difference between the definition of a running-XOR memory and the UT19 implementation (the running-XOR memory checks the number of 1 cells earlier in the memory, whereas the UT19 oddness is based on the number of 1 cells earlier in the cycle, including those in other memories, and on the oddness of the cycle). However, as long as the number of running-XOR memory cells is a power of 2, and sufficiently large, this difference will not matter and the sequence of widths will be undisturbed (because any disturbance will affect all cells within the memory equally, flipping them all, which will have no effect for 2n cycles – and by that time, the program will either have reset or halted). After all, there is a finite limit for how long any Brainpocalypse II program can run without a reset, because a reset is the only way to move the instruction pointer backwards and it will otherwise inevitably reach the end of the program, causing it to halt.
During Command, a program memory cell is represented as [5, 6] (state 0) or [6, 5, 19] (state 1). As usual, the 19 is there purely to give the state 1 program memory cell an odd width, and its empty production has no effect on the following Parity stage. The production of 5 is [7, 9] and the production of 6 is [8, 9] – these are the Parity representations of state-0 and state-1 program memory cells respectively – meaning that if the program memory cell is at an odd position within Command, it will change state, and if it's at an even position, it will remain in the same state, implementing the running-XOR memory behaviour.
During Parity, the program memory cell is represented as [7, 9] (state 0) or [8, 9] (state 1). On an even position within Parity, this will produce from 7 or 8 depending on its state, producing [10, 10] or [11, 10] respectively for Reset. On an odd position within Parity, this will unconditionally produce from 9, producing [18, 10] for Reset. This forgets what state the program memory cell is in, but it doesn't matter, because there are only two reasons why a program memory cell might be in an odd position within Parity: either it's beyond a counter that just decremented from zero (in which case the cell is about to reset, and forgetting which state it was in didn't matter); or as a consequence of the global halt signal (in which case the program is about to end, and again forgetting which state the program memory cells are in doesn't matter).
During Reset, the program memory cell is represented as [10, 10], [11, 10] or [18, 10] (for state 0, state 1, and odd-Parity state, respectively). On an odd Reset cycle, all three cases will produce from 10, which produces [5, 6], the Command representation of a state 0 program memory cell; this means that an odd Reset cycle will reset all the program memory back to its state at the start of the program, implementing the "jump back to the start of the program" behaviour of decrementing 0 in Brainpocalypse II. On an even Reset cycle, this will produce from 10 or 11 depending on the state of the cell, meaning that its state is preserved rather than being reset (11 produces [6, 5, 19], the Command representation of a state 1 program memory cell) – but if the even Reset cycle happens after the component was at an odd position on Parity, this instead produces from 18, the halt symbol. As such, just like the inverters, a program memory cell will immediately produce from 18 when the global halt symbol is received. (If the tag system is not using a halt state, then both the inverters and program memory cells prior to the halt counter will turn into 18s when the halt signal occurs, so everything prior to the halt counter will be either counters or strings of 18s; see #Halt behaviour below for information on how it halts from there.
Counters
In UT19, a counter with value n is represented using a short string of symbols repeated 2n times. The symbols used are those from 12 to 17 inclusive.
One complexity in UT19 comes from a complexity in Brainpocalypse II. Whenever a 0 is decremented in Brainpocalypse II, the implementation is supposed to set the counter value to 1. Counter values are doubled in UT19 in order to allow for the fact that counters can't stay the same (only increment or decrement), so the Command cycles alternate between the "zero value" being 21 and 20 repeats, and thus a counter with value 1 is represented using either 23 or 22 repeats. The problem is that when a counter with value 0 is decremented, it is necessarily being represented as 20 repeats (so that the Parity cycle can detect that the attempt to decrement 0 was made), and thus needs to be represented as 23 once the program resets, which would apparently need a huge production to create such a long string from such a short one.
Instead, a trick is used: during Command, counters remember both their value, and whether they were decremented from 0 last cycle. If they were decremented from 0, the counter increments rather than decrements, even if it is being given a "decrement" command. At the start of the Brainpocalypse II program, a "dummy no-op" is added which decrements and then increments all counters; this will have no effect on most counters, but a counter that was decremented from 0 will instead end up being incremented twice, meaning that only 21 (i.e. 2) repeats are needed for the counter value immediately after reset, rather than 23 (i.e. 8).
As such, there are two representations of counters during Command. If the counter did not just decrement from zero, it is represented as 2n copies of [12, 13]; if the 12 is produced from (i.e. the counter is in an even position, or just decremented from zero), this will increment the counter; if the 13 is produced from (i.e. the counter is in an odd position and did not just decrement from zero), it decrements. This makes it possible to implement a Brainpocalypse II program by using the program memories before, between and after the counters to move the counters to odd or even positions during Command in order to make them increment twice, decrement twice, or decrement then increment (i.e. do nothing), according to what the corresponding command of the Brainpocalypse II program says to do to the counter. (These counter representations both have even widths, meaning that a counter in an odd position will put the subsequent program memory in an odd position; the sequence of widths of each program memory thus needs to be based on the position of the counter before (if any) xor the position of the counter after it (if any). In other words, it can predict whether it will run in an odd or even position because it knows what the previous program memories will do, and account for that when arranging the location of the remaining program memories. This also makes it possible to compensate for the "a Command cycle is odd if the preceding Reset cycle is odd" phenomenon: the very first element in a program memory's sequence (i.e. the width it has immediately after resetting) compensates for the Command cycle being odd (which always happens after, but only after, a reset). (Note that this compensation must itself be compensated for at initial program startup, by starting the program with an odd rather than even Command cycle, which can be done by deleting the first element of the initial string, or alternatively by prepending a 19.)
During Parity, a counter is represented using a single symbol repeated 2n+1 times. If the counter just incremented (producing from 12), the counter will be made out of the symbol 14 (12's production is [14, 14, 14, 14], which produces 2n+1+1 symbols and thus increments the counter from its previous value); if the counter just decremented (producing from 13), the counter will be made out of the symbol 15 (13's production is [15], which produces 2n+1-1 symbols and thus decrements the counter from its previous value). A counter that has just decreased from 0 will therefore consist of 2-1+1 = 1 symbol, and thus have an odd width, causing the subsequent Reset cycle to be odd. (Because Parity cycles always start even, except during halt, and thus will still be even by the time the decrementing counter is reached because a counter that decrements from zero must be the only counter decrementing, the lone 15 will be in one of the positions that produces, rather than one of the positions that is deleted, and thus its production will reliably run despite being only a single symbol wide.)
During Reset, a counter is represented using [16, 16] or [16, 17] repeated 2n times; the [16, 16] representation is used for a counter that just incremented, and [16, 17] for a counter that just decremented (and these are produced from 14 and 15 respectively). Because only half the 14s or 15s produce, this typically leaves the value of the counter the same (half the 2n+1 symbols produce, so there are 2n copies of the resulting production); however, if the counter was decremented from zero, then there was only a single 15 (which produces, i.e. all not half of it produces), so the string is twice as long as it would otherwise be, incrementing the counter back from -1 to 0. In most cases, it is the 16 that will end up producing: this happens if the counter just incremented, if the Reset cycle is even, or both. 16 produces [12, 13], the normal Command representation of a counter, restoring the component to its original state.
If the Reset cycle is odd, and the counter just decremented, then it must have just decremented from zero: oddness during Reset implies that some counter just decremented from zero, and because a no-op is represented as a decrement then increment (rather than the other way round), on cycles where a decrement from zero is possible, only one counter was being decremented. As such, the combination of "some counter decremented from zero" and "this counter just decremented" always implies "this counter just decremented from zero". In this situation, symbol 17 ends up producing, and it expands to [12, 12, 12, 12]. This has the effect of incrementing the counter from 0 to 1 (the production is twice as long as for 16), and because the 13s in the production have been replaced with 12, it will be forced to increment rather than decrement on the next cycle after the reset, so the no-op decrement-all-then-increment-all at the start of the program will raise its value to 3, the correct value for the counter in the doubled Brainpocalypse II program.
Halt behaviour
The program memories are always, individually and collectively, aware of the parity at the start of a Command cycle (because the first element of their memory sequence always runs on an odd Command cycle – it must be just after a reset, otherwise they would be on some later element than the first – and the other elements run on an even Command cycle, because if there had just been a reset, it would be the first element that run). This means that they can conspire to always ensure that a Parity cycle is even (the program memory at the end of the cycle, after the halt counter arranges for this by choosing a width that cancels out the combined oddness of the Command cycle and all the previous program memories). To send the "global halt signal" of oddness during Parity but not Reset, the program memories are arranged to choose the other, nonstandard parity at the end of Command (thus causing an odd Parity cycle), whilst simultaneously decrementing the halt counter from zero (which causes there to be an odd number of symbols within the Parity cycle – everything has an even width apart from the single 15 that represents the halt counter – so the Reset cycle will be even, the opposite parity from what the Parity cycle had). This can easily be added to the point in the program memory sequences immediately after the end of the Brainpocalypse II program, causing UT19 to start to halt at the same point at which the Brainpocalypse II program does.
Unlike with inverters and program memory, the "global halt signal" normally has no effect on counters, leaving them at their previous value. When 18 is a halt symbol, this of course doesn't matter – it's even possible to read the values of the counters from the final state of the queue, and a standard halt is sufficient (a perfect halt is not required). When halting on an empty queue, though, there is a need to clean them up. One thing worth noting is that issuing the global halt signal will end up deleting the halt counter (it is represented by just a single 15 during Parity, but a global halt signal uses an odd Parity cycle and the 15 will end up in an odd position, thus being deleted rather than produced from). The next section will discuss how the counters, and the last section of program memory, are cleaned up in order to produce an empty queue.
On the first Command cycle after a halt signal, the tag system queue will be formed out of a string of 18s, followed by a counter, followed by another string of 18s, another counter, and so on, alternating until the location which previously had the halt counter. After that is the last section of program memory (which was at an even position on the preceding Parity cycle, thus didn't see the halt signal). In order to shrink the queue down to nothing, a trick is used: the lengths of those strings of 18s is almost fully customizable by changing the initial string, because every memory cell and every inverter (before the halt counter) becomes an 18 after the halt signal, and two inverters in a row does nothing. The lengths can thus be set to arbitrary values by adding no-op pairs of inverters, except that the parity of the length on the first cycle is not controllable (because the inverters have to be added in pairs). When 18 is not a halt symbol, its production is [18], which in 2-tag means that every two 18s will produce a single 18: the length of a string of 18s halves each cycle. As such, just like the program memory produces a predictable and controllable sequence of odd widths and even widths while the program is running normally (based on the positions of the inverters relative to the memory cells), the strings of 18s produce a predictable and controllable sequence of odd widths and even widths while the program is halting (based on the number of inverters). The only aspect of this that can't be controlled is the first Command cycle after the halt signal is given. It turns out that if the program starts out with a "decrement all" command (to finish implementing the reset of counters from -1 to 3), all the program memory sections prior to the halt counter will use an even number of inverters, so this forces the "halt program" to start by incrementing every remaining counter (as they will all be at even positions). This isn't a huge problem, though, as the spurious increment command can be cancelled out by giving decrement commands later, and after the first time the lengths of the strings of 18 halves there will now be full control over their parity for the rest of the program.
Given that full control over the widths of the program sections is retained, halting the program from that point is simply a case of sending the last remaining program memory section the halt signal (which can be done easily because it's between two sections of 18s, which can manipulate it to see the "odd on Parity, even on Reset" halt signal), and deleting the remaining counters. Brainpocalypse II has the concept of a "perfect halt" – a halt where all the counters are zero – and it is fortunately Turing-complete even if a perfect halt is the only supported sort of halt (with standard halts being undefined behaviour). Assuming that the construction is compiling from a program which is designed to perfect-halt if it halts at all, the values of all the counters will be known at this point in the program (in the doubled program, they will be made out of 21 repeats on the initial Command cycle and then immediately get spuriously incremented, thus will be at 22 repeats on the next Command cycle). With full control over the oddness/evenness seen on every cycle for the rest of the program, it is then possible to decrement counters down to a single 15, and ensure that 15 is in a deleted rather than produced-from position, causing the counter to disappear. At that point, the entire program will consist of nothing but 18s, and eventually end when there are no 18s left (each step alternates between deleting one 18 and doing nothing, so the queue eventually ends up as [18, 18], which becomes [18] in a produced position, then [18] in a deleted position, and then nothing).
This halt sequence, for reaching a queue of all-18s from a perfect-halt position, requires 11 cycles after the halt signal is given, and thus determines the number of components in each of the program sections, modulo 2048. Here are some concrete values that work, with parities chosen so that they match the parities required to interpret a Brainpocalypse II program (which happen to be "all even, except for the last section which is odd"):
- First program memory section: -2 mod 2048
- Other program memory sections before non-halt counters: 1024 mod 2048
- Program memory section immediately before the halt counter: -68 mod 2048
- Last program memory section (after the halt counter): -23 mod 2048
The program memory section immediately before the halt counter is different from the others because it needs to ensure that the last program memory section is given the global halt signal, whereas the others are responsible for deleting counters rather than program memory.
UT22
UT22 is a variant of UT19 designed to have no empty productions; this causes it to use 22 symbols rather than 19. The two systems are clearly equivalent to each other, so it is Turing-complete for the same reason that UT19 is. UT22 is intended as a demonstration that tag systems can be Turing-complete even without empty productions, whilst retaining a fairly short maximum production length and fairly low number of symbols.
The rules of UT22 are as follows:
[[ 2, 3], [ 4, 4], [18, 4], [19, 1,20], [ 7, 9], [ 8, 9], [10,10], [11,10], [18,10], [ 5, 6], [21, 5,22], [14,14,14,14], [15], [16,16], [16,17], [12,13], [12,12,12,12], [18], [2], [3], [8], [9]]
The only change is that state 19 is removed, and replaced with four states 19, 20, 21, 22. Productions that previously used state 19 (such as symbol 4's production, [1, 1, 19]) are changed to give the same outcome as they did previously in both odd and even positions:
- [1, 1, 19] from UT19 produces [2, 3] in even positions ([2, 3] from 1, [] from 19) and [2, 3] in odd positions ([2, 3] from 1)
[19, 1, 20] from UT22 produces [2, 3] in even positions ([2] from 19, [3] from 20) and [2, 3] in odd positions ([2, 3] from 1) - [6, 5, 19] from UT19 produces [8, 9] in even positions ([8, 9] from 6, [] from 19) and [7, 9] in odd positions ([7, 9] from 5)
[21, 5, 22] from UT22 produces [8, 9] in even positions ([8] from 21, [9] from 22) and [7, 9] in odd positions ([7, 9] from 5)
As such, the only difference between the two tag systems is a small-scale difference in the representation of some productions that only lasts for one cycle.
Some compilers that generate UT19 initial states cannot immediately be used for UT22 because the initial queue has some 19s in it. If a compiler is needed, it would be possible to work around this issue either by modifying the compiler to work with UT22 instead, or by simulating one cycle of the tag system and starting the simulation with Parity (on Parity cycles, the UT19 and UT22 representations of the queue are identical).