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

    [img]
    Preview
    Download (220kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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: https://doi.org/10.1117/12.409212
    Depositing User: Thomas Naughton
    Date Deposited: 04 Jul 2017 14:28
    Journal or Publication Title: Proceedings of SPIE
    Publisher: SPIE
    Refereed: Yes
    URI:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year