Learn THUE with Real Code Examples

Uses string rewriting rules of the form ‘pattern -> replacement’.

Can simulate any Turing-complete computation.

Non-deterministic or deterministic execution depending on rule application.

Primarily theoretical, but has been used to explore formal language theory and computation.

Instructive for understanding the foundations of computation and algorithmic processes.

Alphabet - finite set of symbols

Strings - sequences over the alphabet

Rules - pattern -> replacement transformations

Initial string - starting state of computation

Halting condition - no more applicable rules

Alphabet - set of allowed symbols

String - sequence of symbols

Rule - defines how substrings can be replaced

Initial string - starting point for rewriting

Halting - when no rules match

rules.thue - file defining pattern -> replacement rules

input.txt - initial string(s) to transform

output.txt - resulting strings after computation

logs/ - optional, tracks transformation steps

docs/ - notes on rules and expected behaviors

Define the alphabet

Write the rewriting rules

Set the initial string

Choose execution strategy (deterministic or non-deterministic)

Apply rules until halting or desired output

Beginner: simple string replacement examples

Intermediate: small deterministic Thue programs

Advanced: non-deterministic systems exploring multiple paths

Expert: Turing-complete computation simulations

Architect: formal language and computational proofs

Thue vs Turing Machine: abstract but equivalent computational power

Thue vs Lambda Calculus: string-based vs function-based

Thue vs Post systems: generalization of rewriting systems

Thue vs Regular Expressions: more powerful, Turing-complete

Thue vs Practical languages: educational and theoretical only

1914 - Axel Thue introduces Thue system

1920s–1930s - Expanded in combinatorial word studies

1960s - Recognized as Turing-complete string rewriting system

1970s - Used in formal language theory

1980s - Implemented in simple computational simulators

1990s - Non-deterministic Thue explored in automata research

2000s - Online interpreters and educational tools

2010s - Used in computational theory teaching

2020s - Visualization tools for Thue introduced

2025 - Still mainly academic and theoretical model

Alphabet - symbols used in Thue

String - sequence over alphabet

Rule - transformation instruction

Initial string - starting point for computation

Halting condition - no further rules apply