Welcome to the Thue Reference Manual > What is a Thue? Thue is...uhm...well... OK, I got it. Thue is a language based on the concept of the semi-Thue grammar/process, which is named for (and possibly created by) the Norwegian mathematician Axel Thue (pronounced "TOO-ay"). It is, in essence, an arbitrary grammar, which can (by its arbitrary nature) be used to define/recognize "Type 0" languages from Chomsky's hierarchy. Because the grammar can be used to define a language of such complexity, the process, itself, is essentially Turing Complete. As a result, the Thue language (which, of course, would be much funnier if it rhymed with the Infocom "dark places" creature, but c'est la vie, I guess...) is an arbitrary grammar system, not unlike yacc or a similar beast, except that there is no way to distinguish between a terminal and a nonterminal symbol--they are completely interchangeable. > Write "Thue" with burin. A Thue program consists of two parts: The first part is the set of grammar/production rules, where each rule has the form: lhs::=rhs where the lhs is the string to be recognized, and the rhs is the string which is to replace the lhs. Each string (lhs and rhs) can be completely arbitrary, except that the lhs cannot (for rather obvious reasons) include the production symbol ("::="). The rhs, however, is not restricted in any way. Terminating the rulebase is a production symbol alone on a line, surrounded by (optional) whitespace. Following that is the description of the initial state which Thue will work with. Each line after the rulebase is concatenated to form the initial state. Once loaded, the Thue program nondeterministically applies the rulebase to the current state. It continues to do so until no rules apply to the state (pragmatically, this means that no lhs can be found in the state). > What is a burin? Don't worry about it. It's an Infocom joke. Actually, let's go with it. A burin is tool to inscribe mystical symbols into an object. Thue has one. > Examine burin. Added to this simple system are two strings which are used to permit Thue to communicate with the outside world. The first of these is the input symbol (":::"). The input symbol is actually the lhs of an implicit rule of which the user (or system's "input stream") is a component. The input symbol, therefore, is replaced by a line of text received from the "input stream." As a counterpart of input, the output symbol ("~") is supplied. Like the input symbol, the output symbol triggers an implicit rule which, in this case, encompasses the "output stream." The specific effect is that all text to the right of the output symbol in the rhs of a production is sent to the output stream. Note that either (or both) of these implicit rules may be overridden by providing explicit rules that perform some other task. > Examine Thue. The implementation of Thue, itself, is rather uninteresting, except for three command-line switches: d Activates "Debug Mode," which prints the state immediately after any rule is applied. l Activates "Left Mode," which requires Thue to apply rules deterministically in a left-to-right fashion. r Activates "Right Mode," which is identical to "Left Mode," except that rule application occurs right-to-left. The command-line switches must appear after the Thue filename, and the last incidence of 'l' or 'r' overrides all others. > Look under Thue. Sample programs included are: dec.t Decrements a binary number hello.t Hello, World! inc.t Increments a binary number incany.t Increments a binary number input by the user test.t A simple example to highlight nondeterminism > Amusing. Apologies to Axel Thue for mangling the pronunciation of his name for a cheap joke. Apologies to whatever is left of Infocom for (unknowingly) supplying the format of the cheap joke. > Exit.