Three Star Programmer
Three Star Programmer is an esoteric programming language created by User:ais523 in 2015. It was created when, while working on another esolang, ais523 decided to add an "increment pointed-to address" command, then had problems finding a way to read from memory, and started to wonder whether one was necessary at all or whether an instruction similar to this is sufficient by itself.
Syntax
A Three Star Programmer program is a list of nonnegative integers (conceptually there is no limit on how large these can be, but in practice, it is expected that most programmers will use only small integers). These are written in decimal, separated by whitespace. At the first character in the input file that's neither whitespace nor a decimal digit, the program ends; the rest of the file containing it can freely be used for comments (comments cannot be inserted in the middle of the program).
Semantics
A Three Star Programmer program runs as a single infinite loop; each of the integers in it in turn is treated as a command, and executed in sequence; when the end of the program is reached, it just starts again from the start. There is only one command (making Three Star Programmer an OISC), which takes one argument (because there is only one command, the command does not need a name, and thus giving the argument by itself is possible to specify the whole command).
A Three Star Programmer program stores data in a right-unbounded row of cells, each of which stores a pointer (in the C sense) to itself or to another cell. Initially, all cells are initialized to point at the leftmost cell. The argument to the command is interpreted as an address of one of these cells, with 0 being the leftmost, 1 being the second-leftmost, 2 being the third-leftmost, and so on. When the command executes, it does the following:
- Dereference its argument, to produce the cell it points to;
- Dereference the pointed-to cell, to find the cell that points to;
- Dereference the pointed-to cell, to find the cell that it in turn points to;
- and sets that cell to point at the cell to the right of the cell it currently points to.
Or in C syntax: if the current command is x, we're basically doing (***x)++, thus the name Three Star Programmer. Note that in C, the types for this are quite amusing: C's generic pointer type (that cannot be dereferenced) is void *, and so after two dereferences, a cell needs to be able to point to a pointer (thus must become a generic pointer after three deferences, and is thus a void ****). This makes the array that holds all cells a void *****.
Computational class
"One Star Programmer" is clearly Turing-incomplete, as it can only write to cells mentioned in the original program. Likewise, "Two Star Programmer" can only read cells mentioned in the original program (you can indirectly write arbitrary cells via mentioned pointers, but don't have any way to get at their value, only increment them). Three Star Programmer allows you to read arbitrary cells via indirectly referring to them, then following their pointer and incrementing that cell, which could be one of the cells mentioned in the program, or be involved in some future command; and so it has unbounded data storage, one of the usual requirements to be Turing complete.
Around the time the language was created, ais523 wrote:
That said, it's very hard to actually write anything in the language, because of the fundamental nature of the language, in which everything affects everything else and no change is really reversible. For quite a while, ais523 has been looking to make an esolang in which structured programming is impossible and every program has to be written from scratch. This is probably not that language, and was not designed like that, but may have stumbled closer than any language so far, purely by accident.
However, it was subsequently discovered that "freestart Three Star Programmer" (i.e. Three Star Programmer, but with the memory initialised to a specified pattern rather than all-zeroes) is fairly easy to write in; by choosing some cells to always hold constant values, you can reference via those cells in order to remove one level of indirection (e.g. if cell 5 always holds the value 11, then ***5 is equivalent to **11). With the ability to use one-level and two-level indirections for most things, and the full three levels of indirection only when necessary to read unbounded memory, Three Star Programmer becomes much easier to write in, and it is possible to implement queue-based languages like cyclic tag via similar techniques to those used in the I/D machine Turing-completeness proof.
Dealing with the all-zeroes starting state is painful, but probably not impossible: ais523 has produced a plan for writing programs in Three Star Programmer which makes it very likely that the language is Turing-complete, although this has not yet been formally proven.
Output extension
As an extension, Three Star Programmer interpreters can implement output as follows: treat the second and fourth cells as integers (by considering pointing at the leftmost cell to be 0, the second-leftmost cell to be 1, and so on), and then whenever the second cell is odd at the end of one cycle of execution of the program, output the bottom 8 bits of the fourth cell as a single byte. This extension will not affect the operation of programs that aren't written to use it (although it will quite possibly produce a lot of garbage output).
Examples
0 1 2
Output all bytes counting up from 0, looping forever.
Variants
Because it takes a hell of a lot of work to print anything meaningful in the original incarnation, and because he misunderstood the spec, User:Quintopia inadvertently created a variant, now named "Noisy 3SP", which only differs from the original in that output happens after every command rather than once per cycle. Here is the golfed Python interpreter:
import sys,collections n=list(map(int,sys.stdin.read().split())) d=collections.defaultdict(int) i=0 while 1:d[d[d[n[i]]]]+=1;sys.stdout.write(chr(d[3]%256)if d[1]%2else"");i=(i+1)%len(n);#print[d[k]for k in sorted(d.keys())]
Unbounded cells. Automatically extends memory as needed. Remove the # for debug printing.