Conference Publication Details
Mandatory Fields
Naughton, TJ
CRITICAL TECHNOLOGIES FOR THE FUTURE OF COMPUTING
Continuous-space model of computation is Turing universal
2000
January
Published
1
7 ()
Optional Fields
121
128
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(log(2)n) algorithm for a search problem that has a lower bound of n - 1 on a Turing machine.
Grant Details