=pod =encoding utf8 =head1 DESCRIPTION Cyclic tag systems are one of the simplest-known Turing-complete mathematical models of programming. Compiling cyclic tag systems into a given language is thus often one of the easiest ways to prove that that language is also Turing-complete. The particular concrete representation we use of cyclic tag systems is Bitwise Cyclic Tag. This language operates on a queue of bits (each of which is C<0> or C<1>), and has three commands: =over 4 =item 00 If the head of the queue is C<1>, then enqueue a C<0> bit at the tail of the queue. (Otherwise do nothing.) The C<1> at the head of the queue stays on the queue. =item 01 If the head of the queue is C<1>, then enqueue a C<1> bit at the tail of the queue. (Otherwise do nothing.) The C<1> at the head of the queue stays on the queue. =item 1 Dequeue and discard the bit at the head of the queue. =back The program will run repeatedly, forever, in a loop (there is no flow control beyond the implicit loop around the prorgam). In order to execute a Bitwise Cyclic Tag program, you need to specify the program itself, and an initial queue for it. Thus, this executable takes two arguments: the program and the initial queue. Each is specified as a text file for which all characters other than digits are ignored (allowing them to be used to write comments). C<2> to C<9> inclusive are reserved for extensions. Three Star Programmer, the target language, stores data using a right-infinite tape of pointers, each of which initially points at the leftmost end of the tape. It has only one command, that takes one argument (an integer representing a position on the tape, with C<0> being the leftmost); the command is represented in the input file as a decimal number specifying the argument (as there is only one command, giving the argument alone unambiguously represents the command). Commands are separated by whitespace; comments cannot appear inside the program (but may appear after the program, which ends just before the first non-whitespace non-digit character). When the command executes, the pointer that is pointed to by the pointer that is pointed to by the pointer at the given position on the tape is incremented (causing it to point to the pointer to the right of the pointer it was previously pointing to). As with cyclic tag, there is no flow control beyond an implicit loop around the entire program. Unlike cyclic tag, the initial state of the data array is fixed, and cannot be provided from outside. The purpose of this executable is to compile Bitwise Cyclic Tag into Three Star Programmer, thus proving that Three Star Programmer is Turing-complete. =head1 ALGORITHM =head2 Data storage We allocate the various pointers on the Three Star Programmer tape as follows: =over 4 =item 0 Except at the very start of the first iteration of the program, always points to tape element 2. (The very first thing we do is to run C<0 0> to increment it twice; on future iterations of the program, this will instead increment tape element 2's target twice, which is harmless because after the first iteration, tape element 2 always points to "junk" elements.) =item 1 Used for Three Star Programmer's I/O extension. =item 2 The main pointer for the tape setup during the first iteration; it holds the address of the first tape element that has not yet been fully set up. The setup thus takes place using a series of C<0> (increment tape element 2's target) and C<5> (increment tape element 2 itself) commands. C<5> commands are always given in pairs (thus, on the first iteration, will only change even tape elements). After the first iteration, tape element 2 will be incremented once (indirectly via taepe element 7), and thus from then on, will only end up changing I tape elements from 9 upwards (i.e. junk elements whose values we don't care about), meaning that the first iteration tape setup only really happens once. =item 3 Used for Three Star Programmer's I/O extension. =item 4 During the first iteration, is updated to point at tape element 9, and thereafter never changes. Used as an indirect junk pointer to throw away unwanted increments (via deflecting them to adjust tape element 9, which is never read, only written). =item 5 Always maintained pointing to tape element 0 (i.e. never changed). Because tape element 0 always points to tape element 2, running C<5> will thus increment tape element 2 (no matter where we are in the program, assuming we're outside the first two commands of the first iteration). Tape element 2 is only ever incremented by two at a time (apart from once on the first iteration via a C<7> command); this means that C<5> commands always appear in pairs. =item 6 Queue head pointer; except when it's actively being updated, points to the first element of the queue. Running C<6> will thus increment the tail pointer if the head of the queue is a C<1> bit, or effectively do nothing (because element C<9> gets incremented) if the head of the queue is a C<0> bit. This mechanism makes it possible to read the tape. =item 7 Used to handle the start of the end of the initialization code during the first iteration. At that point, tape element 7 will be pointing to tape element 0, so running C<7> breaks the parity on tape element 2 (changing it to point to an odd element). On iterations after the first, tape element 7 will point to tape element 4, effectively "throwing away" tape element commands. (See the documentation for tape elements 12, 14, and 16 for how it ends up pointing there.) =item 8 Queue tail pointer. Most of the time, this is left pointing to the junk element just after the tail of the queue. The queue format stores a C<0> bit by pointing to the junk tape element 9, and a C<1> bit by pointing here. In order to conditionally enqueue on the tape (i.e. the C<00> and C<01> commands of Bitwise Cyclic Tag), you run C<6> first (thus causing this pointer to point at a fresh tape element if the head of the queue is a C<1> bit, or leaving it pointing to junk otherwise), then a number of C<18> commands equal to the tape position that's desired for the new tape element, then another C<6> command (which is an effective no-op if the head of the queue was a C<0> bit, and restores the invariant on this tape element if the head of the queue was a C<1> bit). =item 9 "Junk" pointer that is never read, only written. Any Three Star Programmer command has to increment some pointer, and unwanted increments are (typically) aimed here in order to get rid of them. (Actually, all odd tape elements from 9 upwards are used like this, in case there's a need to throw away increments via a pointer that has already gone "past" element 9. But 9 is the "main" junk pointer, used whenever there's no reason to use a different one.) =item 10 During the first iteration, is pointed at tape element 6, then stays there all program. Only used indirectly, to increment element 6. =item 12 Used to ensure that the C<7> commands on iterations other than the first will not cause problems. During the initialization of the first iteration, is updated to point at tape element 7 (via the standard C<0> and C<5> mechanism). Code at the end of the initialization, that runs on every iteration, increments it twice more (thus moving it gradually through the junk elements: 9, 11, and so on), using two C<16> commands. =item 14 During the first iteration, is pointed at tape element 12, then stays there for the rest of the program. C<14> thus increments tape element 7 on the first iteration, and junk on subsequent iterations. It is given four times near the end of initialization (but before the C<16> commands are run); this means that tape element 7 will point to tape element 0 during initialization on the first iteration, and tape element 4 from then on. =item 16 During the first iteration, is pointed at tape element 14, then stays there all program. C<16> thus increments tape element 12 on any iteration, and is run twice (right at the end of the initialization) in order to cause tape element 12 to point to junk once the initialization is over. =item 18 During the first iteration, is pointed at tape element 8, then stays there all program. C<18> will thus increment a fresh element at the tail of the queue (while one is being created using C<6>), and have no real effect (due to incrementing a junk element) otherwise. =item 20 During the first iteration, is pointed at tape element 10, then stays there all program. A C<20> command will thus increment tape element 6, meaning that C<20 20> will discard the first element of the queue. =item 22 The initial queue starts here (and this and all subsequent even tape elements are used for the queue). =back =head2 Structure of the program We can now write the program in a kind of Three Star Programmer pseudocode (with an invented comment syntax to make it possible to see what's going on): # Start by getting tape pointers 0 and 2 set up correctly 0 0 5 5 5 5 # Set up the even tape elements as required 0 0 0 0 0 0 0 0 0 5 5 # 4 at 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 # 6 at 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 5 5 # 8 at ... 0 0 0 0 0 0 5 5 # 10 at 6 0 0 0 0 0 0 0 5 5 # 12 at 7 0 0 0 0 0 0 0 0 0 0 0 0 5 5 # 14 at 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 # 16 at 14 0 0 0 0 0 0 0 0 5 5 # 18 at 8 0 0 0 0 0 0 0 0 0 0 5 5 # 20 at 10 # The initial queue is also on even elements. # This means we can initialize it the same way ... # (Permanently) turn off first-iteration special cases # Causes both the initialization code above, and itself, to do # nothing of consequence from now on. 7 14 14 14 14 16 16 # Now come the BCT commands. Here's what a 00 looks like... 6 18 18 18 18 18 18 18 18 18 6 # ...here's a 01... 6 18 18 18 18 18 18 18 18 6 # ...and here's a 1. 20 20 As can be seen, the program is mostly fixed in content. First we encode a fixed section, then one small variable section (element 8) that encodes the initial length of the queue, then another fixed section, then the initial queue itself, then another fixed section, and then finally the commands from the BCT program. (Giving these multiple times would help with efficiency because the initialization code has to run, doing nothing useful, each time round the loop. However, we don't replicate them as of right now to make the construction as clear as possible.)