Clue (Keymaker)

From Esolang
Jump to navigation Jump to search
You may be looking for the other language named Clue (by oklopol).
Program string 110 run for 5000 cycles.

Clue is a simple, cyclic esoteric programming language, created in 2009 by User:Keymaker. The computational class of the language is unknown but the author thinks it is not Turing-complete. A Clue program is a string consisting only of 0s and 1s. There is no separate memory; the program string modifies itself every time an instruction is executed. There is a program pointer that initially starts in the beginning of the string, moving forward after every instruction, returning to the beginning when reaching the end of the string. One executed instruction is one cycle in Clue terminology. The program halts if it becomes the empty string.

  • 0 removes the last character of the string.
  • 1 takes the next two characters, NANDs them (resulting 0 if both inputs 1, otherwise 1), and adds the result in the beginning of the string. The program pointer then moves to just beyond the second input that was read for NAND.

For example, the program 110 (nothing to do with the famous cellular automata rule 110) would work the following way (x marks where the program pointer is currently):

1x 1 0 (1 and 0 is NANDed, the resulting 1 is placed in the beginning)
1x 1 1 0 (1 NAND 1, 0 added in the beginning)
0 1 1 1 0x (the last character is removed, thus the 0 removes itself)
0x 1 1 1 (the last character, 1, is removed)
0 1x 1 (1 NAND 0, 1 is added in the beginning -- and so forth...)

The visualization of the state of the program string for the first 5000 cycles is seen on right. The white cells mark 0s, the black cells mark 1s.

Finite formations

The 574 cycles of 010001011011.

Finite formations, in Clue, are programs that end. Using a program to comb through some 20000 first programs (0, 1, 00, 01, 10, 11, 000, 001, ...), each allowed to run for 100000 cycles, reveals a relatively small amount of such programs. Most such programs are simple, not reaching 30 cycles. Occasionally, however, there are programs that start growing, yet at a certain point the growth reversals, then reversals again but the growth is feebler, until it stagnates again. Here are some of the longer ones (the program / on which cycle it ends):

  • 101111101 / 557
  • 0100010111 / 572
  • 1011111010 / 558
  • 1101000100 / 568
  • 01000100000 / 573
  • 10111110100 / 559
  • 11011011010 / 609
  • 010001001000 / 574
  • 101101111101 / 554
  • 101111101000 / 560
  • 101111101001 / 560
  • 110100001000 / 570
  • 1101101101001 / 613

Some formations grow only once and stagnate fast towards their end:

  • 0100011011111 / 289
  • 0110110010100 / 283
  • 1111010111001 / 137
  • 0110100101101 / 69

Then there are the simplest formations that never grow any:

  • 000000010000 / 12

Needless to say, there may well be finite formations among the first programs that only reveal themselves after they are run more than 100000 cycles.

External resources

  • Clue page (the specs, very simple programs, visualizations, an interpreter, a graphical viewer)