Continuous-space model of computation -- an introduction

• Inspired by the theory of physical optics

• The basic data unit is a two-dimensional complex-valued function (positive, single-valued, continuous in both dimensions)

• Properties:
  • at least as (computationally) powerful as the Turing machine model,
  • super-Turing capabilities, and
  • exponential reductions in computational complexity for specific problems

• Theory of physical optics does not preclude an implementation

Description

• The memory is divided into a finite grid of images
  

• Images can be copied, moved, and rescaled.
  

• The primitive operations of our model include Fourier transformation, image addition, and image multiplication

System

• We have emulated a general-purpose computer with our model
  
  

• Super-Turing capabilities (analog recurrent neural network simulation) and computational complexity advantages (log₂ n unordered searching) have been demonstrated

References

• Woods and Naughton, "An optical model of computation," Theoretical Computer Science, vol. 334, no. 1-3, pp. 227-258, April 2005. (© Elsevier.)
• Naughton and Woods, "On the computational power of a continuous-space optical model of computation," Lecture Notes in Computer Science vol. 2055, 288-299, 2001. (© Springer-Verlag.)
• Naughton, "Continuous-space model of computation is Turing universal," Proc. SPIE vol. 4109, 121-128, 2000. (© SPIE.)
• Naughton, "A model of computation for Fourier optical processors," Proc. SPIE vol. 4089, 24-34, 2000. (© SPIE.)

URL: http://www.cs.nuim.ie/~tnaughton/abc
Last updated: August 2005
Contact: