17 November 2000 Continuous-space model of computation is Turing universal
Author Affiliations +
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.
© (2000) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Thomas J. Naughton, Thomas J. Naughton, "Continuous-space model of computation is Turing universal", Proc. SPIE 4109, Critical Technologies for the Future of Computing, (17 November 2000); doi: 10.1117/12.409212; https://doi.org/10.1117/12.409212
PROCEEDINGS
8 PAGES


SHARE
Back to Top