Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE
Continuous-space model of computation is Turing universal
Thomas J. Naughton
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.