MURAL - Maynooth University Research Archive Library



    Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines


    Woods, Damien and Neary, Turlough (2015) Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, 137. pp. 1-9. ISSN 0169-2968

    [img]
    Preview
    Download (166kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don’t yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii’s other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.

    Item Type: Article
    Keywords: Yurii Rogozhin; contribution; Small Universal Turing machines; small circular Post machines;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Electronic Engineering
    Faculty of Science and Engineering > Experimental Physics
    Faculty of Science and Engineering > Mathematical Physics
    Faculty of Science and Engineering > Mathematics and Statistics
    Faculty of Science and Engineering > Psychology
    Faculty of Science and Engineering > Research Institutes > Callan Institute
    Faculty of Science and Engineering > Research Institutes > Centre for Ocean Energy Research
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 13730
    Identification Number: https://doi.org/10.3233/FI-2015-1198
    Depositing User: Damien Woods
    Date Deposited: 01 Dec 2020 17:08
    Journal or Publication Title: Fundamenta Informaticae
    Publisher: IOS Press
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year