We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Thue Symbol Sorting Theorem
Safalra's Special Thue Symbol Sorting Theorem (SSTSST) and Safalra's General Thue Symbol Sorting Theorem (SGTSST) place a lower bound on the speed of symbol sorting in Thue in terms of the number of string replacements made - namely that sorting is Omega(n^2), where n is the number of symbols to sort.
Terminology
- Bounded sorting - Sorting a number of items, each with bounded length
- Symbol sorting - Sorting a number of items, each of which is a single symbol
- Permutation symbol sorting - Sorting a number of items, each of which is a single symbol, using rules whose right-hand sides are permutations of their left-hand sides
Because a Thue program can only deal with a finite number of symbols, there are a finite number of possible items whose length is less than a fixed value. This means that bounded sorting can be converted into symbol sorting in Theta(n) time by converting each item into a single symbol.
The theorems
- Safalra's Special Thue Symbol Sorting Theorem - Permutation symbol sorting of n items runs in Omega(n^2) time
- Safalra's General Thue Symbol Sorting Theorem - Symbol sorting of n items runs in Omega(n^2) time
The proofs are complex and are not provided here.
External resources
- Sorting In Thue (dead link) - contains a proof of Safalra's Special Thue Symbol Sorting Theorem