Thue (programming language)

Thue (/ˈtuːeɪ/ TOO-ay) is an esoteric programming language invented by John Colagioia in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy. Because it is able to define languages of such complexity, it is also Turing-complete itself. Thue is based on a nondeterministic string rewriting system called semi-Thue grammar, which itself is named after the Norwegian mathematician Axel Thue; inspiration is also taken from the grue. The author describes it as follows: "Thue represents one of the simplest possible ways to construe constraint-based programming. It is to the constraint-based paradigm what languages like OISC are to the imperative paradigm; in other words, it's a tar pit."

A Thue program starts with a rulebase, which is a series of substitution rules, each of this form:

The rulebase terminates with a lone production symbol on a line:

The initial state is a series of symbols which follow the rulebase.

Thue consumes the initial symbols and substitutes the result of the rules for each of the initial state's symbols.