MURAL - Maynooth University Research Archive Library



    Thue's 1914 paper: a translation


    Power, James F. (2013) Thue's 1914 paper: a translation. Working Paper. arXiv.

    [thumbnail of JP-Thue-translation-2013.pdf]
    Preview
    Text
    JP-Thue-translation-2013.pdf

    Download (249kB) | Preview

    Abstract

    This paper includes notes to accompany a reading of Thue's 1914 paper "Probleme uber Veranderungen von Zeichenreihen nach gegebenen Reglen", along with a translation of that paper. Thue's 1914 paper is mainly famous for proving an early example of an undecidable problem, cited prominently by Post. However, Post's paper principally makes use of the definition of Thue systems, described on the first two pages of Thue's paper, and does not depend on the more specific results in the remainder of Thue's paper. 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: Monograph (Working Paper)
    Keywords: Thue; history of computing; formal language theory; algorithms;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 10225
    Depositing User: Dr. James Power
    Date Deposited: 16 Nov 2018 16:10
    Publisher: arXiv
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/10225
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads