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.
Keywords: analog computation, real computation, optical information processing, computability, computational complexity, models of computation, Fourier transform processor, general-purpose optical computer.
|
|
Copyright 2000 Society of Photo-Optical Instrumentation Engineers.
This paper was published in the Proceedings of SPIE volume 4109 and is made available as an electronic reprint with permission of SPIE. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper are prohibited.
|
© SPIE.
