MURAL - Maynooth University Research Archive Library

    Continuous-space model of computation is Turing universal

    Naughton, Thomas J. (2000) Continuous-space model of computation is Turing universal. Proceedings of SPIE, 4109. pp. 121-128. ISSN 0277-786X

    Download (220kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    Our model of computation (theoretical machine) was designed for the analysis of analog Fourier optical processors, its basic data unit being a continuous image of unbounded resolution. In this paper, we demonstrate the universality of our machine by presenting a framework for arbitrary Turing machine simulation. Computational complexity benefits are also demonstrated by providing a O(log2n) algorithm for a search problem that has a lower bound of n - 1 on a Turing machine.

    Item Type: Article
    Keywords: analog computation; real computation; optical information processing; computability; computational complexity; models of computation; Fourier transform processor; general-purpose optical computer;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8402
    Identification Number:
    Depositing User: Thomas Naughton
    Date Deposited: 04 Jul 2017 14:28
    Journal or Publication Title: Proceedings of SPIE
    Publisher: SPIE
    Refereed: Yes
      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