**Thue Systems** - **Core Idea:** Manipulation of symbolic sequences using production rules. - **Example Rule:** "ab" -> "ba" (This rule would swap every occurrence of 'ab' within a string) - **Key Questions:** Thue investigated the existence of infinite non-repetitive sequences under certain rule systems (square-free words being an example). **Connections** 1. **Thue Systems & Post Systems:** - **Generalization:** [[Post production systems]] can be seen as a generalization of Thue systems. Post systems also have string manipulation rules, but they provide more flexibility in their format and the types of operations allowed. - **Historical:** Thue's work on semi-Thue systems influenced Emil Post, who developed Post systems to further explore the boundaries of computability and formal systems. 2. **Thue Systems & Kleene's Work:** - **Regular Expressions:** The study of Thue systems shares a common root with regular expressions, a fundamental tool for specifying patterns in text. Both focus on symbolic manipulation and pattern recognition. - **Computational Power:** Thue systems, while seemingly simple, are computationally equivalent to Turing machines. This connection was investigated in the work of Kleene, who explored the power of different formal models of computation. 3. **Thue Systems & Lambda Calculus:** - **Rewriting Systems:** Both Thue systems and lambda calculus belong to the broad family of rewriting systems, where the focus is on transforming expressions according to defined rules. - **Combinatory Logic:** The concept of substitution, central to Thue systems, is closely related to the field of combinatory logic, which also informs lambda calculus. - **Computability:** While Thue systems focused on string manipulation, lambda calculus delved into the fundamental nature of computation itself. However, both contributed to our understanding of which operations can be effectively carried out within formal systems. **Overall** - Thue systems represent an early exploration of symbolic manipulation and formal systems. While outwardly simple, they revealed a surprising level of expressivesiveness and power. - They influenced and are connected to later developments in theoretical computer science, including Post production systems, regular expressions, and the study of computability, including important contributions by Kleene and the development of lambda calculus. - # References ```dataview Table title as Title, authors as Authors where contains(subject, "Thue") or contains(subject, "Kleene") or contains(subject, "Lambda Calculus") ```