Simulating Turing machines on Maurer machines

J.A. Bergstra, C.A. Middelburg

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)

    Abstract

    In a previous paper, we used Maurer machines to model and analyse micro-architectures. In the current paper, we investigate the connections between Turing machines and Maurer machines with the purpose to gain an insight into computability issues relating to Maurer machines. We introduce ways to simulate Turing machines on a Maurer machine which, dissenting from the classical theory of computability, take into account that in reality computations always take place on finite machines. In one of those ways, multi-threads and thread forking have an interesting theoretical application.
    Original languageEnglish
    Pages (from-to)1-23
    JournalJournal of Applied Logic
    Volume6
    Issue number1
    DOIs
    Publication statusPublished - 2007

    Fingerprint Dive into the research topics of 'Simulating Turing machines on Maurer machines'. Together they form a unique fingerprint.

    Cite this