Thue ( ) 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
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any ...
itself. Thue is based on a
nondeterministic string rewriting system
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ...
called
semi-Thue grammar
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ...
, which itself is named after the
Norwegian
Norwegian, Norwayan, or Norsk may refer to:
*Something of, from, or related to Norway, a country in northwestern Europe
* Norwegians, both a nation and an ethnic group native to Norway
* Demographics of Norway
*The Norwegian language, including ...
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Axel Thue
Axel Thue (; 19 February 1863 – 7 March 1922) was a Norwegian mathematician, known for his original work in diophantine approximation and combinatorics.
Work
Thue published his first important paper in 1909.
He stated in 1914 the so-calle ...
. 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
Oisc (also Æsc or Esc, pronounced “oish” or “ash”) was an early king of Kent who — according to the Anglo-Saxon Chronicle — ruled from 488-512CE. He seems to be the same person as Ansehis (or Anschis) who is described as a leader o ...
are to the imperative paradigm; in other words, it's a
tar pit
Tar pits, sometimes referred to as asphalt pits, are large asphalt deposits. They form in the presence of oil, which is created when decayed organic matter is subjected to pressure underground. If this crude oil seeps upward via fractures, cond ...
."
Production rules
A Thue program starts with a rulebase, which is a series of substitution rules, each of this form:
''lhs'' ::= ''rhs''
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.
Thue terminates when lhs cannot be found in a resultant state.
Notes
*''::='' is pronounced ''can be''.
*''lhs'' is "left hand side".
*''rhs'' is "right hand side".
*"''::=''" can never be the lhs.
*":::" is an input stream.
*"~" is the output stream.
* Semi-Thue systems are isomorphic to
unrestricted grammar In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted gram ...
s.
Calling Thue
When invoked with 'd' (debug), print the state.
When invoked with 'l' (left side), apply the rules left-to-right.
When invoked with 'r' (right side),
apply the rules right-to-left.
The last 'l' or 'r' overrides the previous switches.
Sample programs
Here is the traditional "Hello World!" in Thue:
a::=~Hello World!
::=
a
The following Thue program performs an increment of a binary number entered as the initial state surrounded by "_" characters, in this case the number 1111111111:
1_::=1++
0_::=1
01++::=10
11++::=1++0
_0::=_
_1++::=10
__::=1
::=
_1111111111_
The following sample program is to demonstrate Thue's nondeterminism (and to show an example of an infinite loop, besides). The program outputs bits in an undefined (and quite possibly random) sequence.
b::=~0
b::=~1
ac::=abc
::=
abc
See also
*
Markov algorithm
External links
The Thue Programming LanguageThue at the Esolang wikiBlog post on Thue
Esoteric programming languages
Programming languages created in 2000
{{compu-lang-stub