Clue is a deterministic esoteric programming language with a cyclic nature. It has no input or output, but inspecting its execution is quite fascinating (at least to the author). The language was created in 2009 by Keymaker, rather spontaneously -- it was as if the language designed itself -- in about one day. The author has no idea of its computational class.

A Clue program is a finite binary string (zero-length also alright) of 0s and 1s. There is no separate memory, the program is self-modifying. The program string alters in execution, and if it becomes the empty string, the execution ends -- the program halts. Which does not to seem happen too often.

The instructions work in the following way.
0 removes one instruction from the end of the program string.
1 reads the next two characters, A and B, and performs a NAND ('not and') using them and places the result in front of the program string. (If both A and B are 1, the result is 0, otherwise it is 1.) Notice that despite data being added in the beginning, the position of the program pointer stays in its place, and moves forward from that place.

The cyclical nature of the language, the program pointer moving from left to right, means that if 1 is executed, for example, as a last instruction of the program string, it will get the two values it needs from the beginning of the string -- and then the program pointer moves to the following character after the data. An example execution below.

0x 1 1 (0 removes the right-most character, 1)
0 1x (reads 0 and 1 as A and B, as the characters, cyclically, following 1 are 0 and 1 in this program; 0 NAND 1 is 1, so 1 is placed in the beginning of the program; program pointer moves one forward (from the last character, from which B data was read, 1), and thus wraps in to the beginning)
1x 0 1 (0 and 1 are taken for NAND, and so on...)

Below is one more, even if the above might have been enough already.

1x 0 (0 NAND 1 is 1, which is added in the beginning)
1 1 0x (the last character is removed, in this case the 0 removes itself)
1x 1 (1 NAND 1 is 0, which is placed in the beginning)
0 1 1x (0 NAND 1 is 1, and so forth...)


Here are a few programs equipped with their visualizations. White pixels mark 0s and black pixels mark 1s. A shade of gray is used for the background -- it is empty space where the Clue program does not reach on the row that has it.

b.cue (a.cue reversed)
c.cue (a.cue inverted)
below their visualizations (1000 cycles each) for comprison

111.cue (traced for 3000 cycles) -- notice the interesting change when it looks like the program is heading towards its termination yet it does not, after all

295.cue -- a program that lasts 295 cycles, creating a finite formation

841.cue which grows heavily (for 5000 first cycles see here)


In this language programming is secondary, more interesting is to create beautiful formations which the program execution seems to create. I was much surprised how 'harmonious' the execution seems to be.

Different alternatives for the NAND operation were tried, yet NAND was the first one I thought of and tried -- and obviously the best one, and was thus chosen. It creates the most interesting 'output', in my opinion. Only one combination of the four creating 0s, the others 1s, ensures (at least so it seems) that there will be a good balance of destructive 0-instructions and 1s which will expand the program further. Somehow I found it fitting, also, that two 'truth' values create 'false' -- that was more or less the decision behind the operation, initially, NAND only happens to be a known name for it.

I have no idea whether some of the seemingly ever-increasing programs sometime start shrinking and finally terminate. There could be at least some. Or could there?

Are there any programs with periodic patterns? Some alternatives of NAND operation, in the design phase, made such programs form easily.

Often the width of a visualization will not be even half of its height.


An interpreter, written in Perl, can be found here. (Rename it to .pl.) Give the Clue program file as an argument. If you want to run the interpreter only a defined number of cycles (useful for collecting data for a visualization, for example), give the interpreter an extra argument, a non-negative integer -- the interpreter will then run only that amount of cycles. The interpreter outputs the state of the program in the beginning of every cycle. In case the program halts, the interpreter tells on which cycle the program string was empty (0 is the very first cycle).

ClueView is a Python program, using pygame, which creates a visualization, given as input a Clue program output. The images above were created with this program. Give the program as an argument the file in which the data can be found. As a second, voluntary, argument you may give a name, and the program will save the created image as a .png picture with the given name.

-- Keymaker, 27.9.2009