The Thue-Morse sequence is an infinite, apparently simple binary sequence which attracts interests in several branches of mathematics since Axel Thue studied it. [1] offers a good introduction to the intriguing aspects of the sequence.
An esoteric programming language named after him also exists. The language's execution model is a string rewriting system called semi-Thue system. Unlike unrestricted grammars, a mixture of terminals and non-terminals is allowed for the internal state of the model.
Today we have published an C++ implementation, called thue, of the Thue language's interpreter: https://github.com/fixedpoint/thue
For example the following Thue program prints the Thue-Morse sequence indefinitely unless interrupted.
@0::=0@
@1::=1@
*0::=0x*
*1::=1o*
*|::=|
o|::=|o
o0::=0o
o1::=1o
x|::=|x
x0::=0x
x1::=1x
o#::=#0
x#::=#1
@|#0::=0@|#
@|#1::=1@|#
@|#]::=_|#]
0_::=_0
1_::=_1
<0::=0<>0
<1::=1<>1
<_::=_<
>_::=_>
x<::=<x
o<::=<o
*<::=<*
@<::=<@
>0::=~0
>1::=~1
[_::=[@*
::=
[@*<0|#]
Saving the above code in a file seq.t, you can print an initial segment of the sequence by running thue with the -s command-line option to limit the number of steps at which the production rules are applied:
% ./thue -s 5000 seq.t
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
[1] Allouche et al. 1999. The Ubiquitous Prouhet-Thue-Morse Sequence, in: Ding, C., Helleseth, T., Niederreiter, H. (Eds.), Sequences and Their Applications. Springer London, London, pp. 1–16. doi:10.1007/978-1-4471-0551-0_1