An optical model of computation. (English) Zbl 1080.68030
Summary: We prove computability and complexity results for an original model of computation called the continuous space machine. Our model is inspired by the theory of Fourier optics. We prove our model can simulate analog recurrent neural networks, thus establishing a lower bound on its computational power. We also define a \(\Theta(\log_2 n)\) unordered search algorithm with our model.
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68P10 | Searching and sorting |
Keywords:
Continuous space machine; Unconventional model of computation; Analog computation; Optical computing; Computability; Computational complexity; Analog recurrent neural network; Fourier transform; Binary search; Unordered searchReferences:
| [1] | Balcázar, J. L.; Díaz, J.; Gabarró, J., Structural complexity, (EATCS Monographs on Theoretical Computer Science, vols. I and II (1988), Springer: Springer Berlin) · Zbl 0574.68039 |
| [2] | Bennett, C. H.; Bernstein, E.; Brassard, G.; Vazirani, U., Strengths and weaknesses of quantum computing, SIAM J. Comput., 26, 5, 1510-1523 (1997) · Zbl 0895.68044 |
| [3] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1997), Springer: Springer New York · Zbl 0948.68068 |
| [4] | Blum, L.; Shub, M.; Smale, S., A theory of computation and complexity over the real numbersNP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., 21, 1-46 (1989) · Zbl 0681.03020 |
| [5] | M.L. Campagnolo, Computational complexity of real valued recursive functions and analog circuits, Ph.D. Thesis, Instituto Superior Técnico, Universidade Técnica de Lisboa, 2001.; M.L. Campagnolo, Computational complexity of real valued recursive functions and analog circuits, Ph.D. Thesis, Instituto Superior Técnico, Universidade Técnica de Lisboa, 2001. |
| [6] | Chen, F. S.; LaMacchia, J. T.; Fraser, D. B., Holographic storage in lithium niobate, Appl. Phys. Lett., 13, 7, 223-225 (1968) |
| [7] | Chiou, A. E., Photorefractive phase-conjugate optics for image processing, trapping, and manipulation of microscopic objects, Proc. IEEE, 87, 12, 2074-2085 (1999) |
| [8] | Goodman, J. W., Operations achievable with coherent optical information processing systems, Proc. IEEE, 65, 1, 29-38 (1977) |
| [9] | Goodman, J. W., Introduction to Fourier Optics (1996), McGraw-Hill: McGraw-Hill New York |
| [10] | Grover, L. K., A fast quantum mechanical algorithm for database search, (Proc. 28th Annu. ACM Symp. Theory of Computing (1996)), 212-219 · Zbl 0922.68044 |
| [11] | Knuth, D., Sorting and Searching, (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [12] | Moore, C., Recursion theory on the reals and continuous-time computation, Theoret. Comput. Sci., 162, 1, 23-44 (1996) · Zbl 0871.68027 |
| [13] | Naughton, T. J., A model of computation for Fourier optical processors, (Lessard, R. A.; Galstian, T., Optics in Computing 2000, Proc. SPIE, Vol. 4089 (2000), Quebec: Quebec Canada), 24-34 |
| [14] | Naughton, T.; Javadpour, Z.; Keating, J.; Klíma, M.; Rott, J., General-purpose acousto-optic connectionist processor, Opt. Eng., 38, 7, 1170-1177 (1999) |
| [15] | Naughton, T. J.; Woods, D., On the computational power of a continuous-space optical model of computation, (Margenstern, M.; Rogozhin, Y., Machines, Computations and Universality; 3rd Internat. Conf., Lecture Notes in Computer Science, Vol. 2055 (2001), Springer: Springer Berlin), 288-299 · Zbl 0984.68507 |
| [16] | Pu, A.; Denkewalter, R. F.; Psaltis, D., Real-time vehicle navigation using a holographic memory, Opt. Eng., 36, 10, 2737-2746 (1997) |
| [17] | Rojas, R., Conditional branching is not necessary for universal computation in von Neumann computers, J. Universal Comput. Sci., 2, 11, 756-768 (1996) · Zbl 0960.68579 |
| [18] | Siegelmann, H. T., Neural networks and analog computationbeyond the Turing limit, Progress in Theoretical Computer Science (1999), Birkhäuser: Birkhäuser Boston · Zbl 0912.68161 |
| [19] | Siegelmann, H. T.; Sontag, E. D., Analog computation via neural networks, Theoret. Comput. Sci., 131, 2, 331-360 (1994) · Zbl 0822.68029 |
| [20] | VanderLugt, A., Signal detection by complex spatial filtering, IEEE Trans. Inform. Theory, IT-10, 139-145 (1964) · Zbl 0116.35306 |
| [21] | VanderLugt, A., Optical Signal Processing, Wiley Series in Pure and Applied Optics (1992), Wiley: Wiley New York |
| [22] | Wang, P.-Y.; Saffman, M., Selecting optical patterns with spatial phase modulation, Opt. Lett., 24, 16, 1118-1120 (1999) |
| [23] | Weaver, C. S.; Goodman, J. W., A technique for optically convolving two functions, Appl. Opt., 5, 7, 1248-1249 (1966) |
| [24] | Weihrauch, K., Computable AnalysisAn Introduction, Texts in Theoretical Computer Science (2000), Springer: Springer Berlin · Zbl 0956.68056 |
| [25] | Yu, F. T.S.; Lu, T.; Yang, X.; Gregory, D. A., Optical neural network with pocket-sized liquid-crystal televisions, Opt. Lett., 15, 15, 863-865 (1990) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
