symbol sequences according to given rules

Zeichenreihen nach gegebenen Regeln

Axel Thue's paper of 1914 on string rewriting was made famous by Emil Post when, in 1947, he proved the word problem for Thue systems to be undecidable. Yet, only the first two pages of Thue's paper are directly relevant to Post's work in 1947, and the remaining 30 pages seem to have been cast into the shade. |

Thue's paper has been "passed by reference" into the history of computing, based mainly on a small section of that work. A closer study of the remaining parts of that paper highlight a number of important themes in the history of computing: the transition from algebra to formal language theory, the analysis of the "computational power" (in a pre-1936 sense) of rules, and the development of algorithms to generate rule-sets. |

- In a paper at
*Computability in Europe 2014*I reviewed some algorithmic elements of Thue's paper: here's a preprint of this and the sides from the talk. -
I also gave an overview of Thue's work in
an extended abstract at the
*2nd International Conference on the History and Philosophy of Computing*, 28-31 Oct 2013, Paris, France. - I've put an English translation of Thue's paper (the original is in German) and some note on arxiv.org as arXiv:1308.5858
- As regards Thue's other papers:
- the 1906/1912 pair have been discussed and translated by Jean Berstel,
- the 1910 paper, a kind of prequel to the 1914 paper, has been described by M. Steinby and W. Thomas
- Thue's mathematical work was recently the focus of a conference celebrating the 150th anniversary of his birth: Thue 150