Talk:Thue Symbol Sorting Theorem

Original website text (was http://safalra.com/programming/esoteric-languages/thue/sorting-theorems/)

This page details some theorems concerning the time complexity of sorting algorithms in Thue. The time complexity relates the number of steps required to sort the data to the number of items to be sorted. This is only well defined for bounded sorting, including symbol sorting:

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

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 Θ(n) time by converting each item into a single symbol.

The simplest form of symbol sorting works by exchanging adjacent symbols, running in Θ(n2) time. The following program performs this with the symbols ‘a’, ‘b’, ‘c’ and ‘d’:

ba::=ab ca::=ac cb::=bc da::=ad db::=bd dc::=cd

The first sorting theorem puts a lower limit on the time complexity of permutation symbol sorting algorithms, and shows that algorithms like that above are the best possible.

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

Safalra’s Special Thue Symbol Sorting Theorem

Permutation symbol sorting of n items runs in Ω(n2) time

Proof of Safalra’s Special Thue Symbol Sorting Theorem

Let the maximum length of the land-hand side (or right-hand side) of any rule be k. Without loss of generality the symbols 0 are 1 are among those that can be sorted, and 0 comes before 1. Case 1: n is even

Let m=n÷2. Consider sorting the string consisting of m 1s followed by m 0s. Without loss of generality, the different 0s are in the same order after sorting as before, and the same is true of the 1s. Therefore each 0 or 1 must move m places, which takes at least m÷(k−1) moves. There are 2m symbols to move, and in each step at most k symbols will move. Therefore at least 2m2÷(k(k−1)) steps are required. Case 2: n is odd

Let m=(n−1)÷2. Consider sorting the string consisting of m 1s followed by m+1 0s. Without loss of generality, the different 0s are in the same order after sorting as before, and the same is true of the 1s. Therefore each of the m+1 0's must move m places, which takes at least m÷(k−1) moves. Each of the m 1's must move m+1 places, which takes at least (m+1)÷(k−1) moves. In each step at most k symbols will move. Therefore at least 2(m2+m)÷(k(k−1)) steps are required.

In both cases the number of steps is Ω(n2).

Safalra’s General Thue Symbol Sorting Theorem

The general version of the theorem states that sorting n items, each of which is a single symbol, runs in Ω(n2) time, whatever method is used. The proof is difficult — it basically shows that in the worst case the data string is of length Ω(n) at all points during the algorithm, and then a similar argument to that above applies, except that the original symbols are ‘contained within’ the new symbols.