MURAL - Maynooth University Research Archive Library

    Exploring Thue's 1914 paper on the transformation of strings according to given rules

    Power, James F. (2013) Exploring Thue's 1914 paper on the transformation of strings according to given rules. In: HaPoC 2013 : 2nd International Conference on the History and Philosophy of Computing 2013, 28-31 Oct 2013, Paris.

    Download (138kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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. Based on a recently completed translation of this paper, I hope to shed some light on the remaining part of this work, and to advocate its relevance for the history of computing. 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.

    Item Type: Conference or Workshop Item (Paper)
    Keywords: Thue systems; strings; string rewriting;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 6374
    Depositing User: Dr. James Power
    Date Deposited: 22 Sep 2015 15:02
    Refereed: No
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads