Continuous-space model of computation is Turing universal
SPIE, San Diego, 1 August 2000
Tom Naughton, Department of Computer Science, NUI Maynooth, Ireland
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(log2 n) algorithm for a search problem that has a lower bound of n-1 on a Turing machine.