Naughton, Thomas J. (2000) Continuous-space model of computation is Turing universal. Proceedings of SPIE, 4109. pp. 121-128. ISSN 0277-786X

Preview

Download (220kB) | Preview

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.

Item Type:	Article
Keywords:	analog computation; real computation; optical information processing; computability; computational complexity; models of computation; Fourier transform processor; general-purpose optical computer;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	8402
Identification Number:	https://doi.org/10.1117/12.409212
Depositing User:	Thomas Naughton
Date Deposited:	04 Jul 2017 14:28
Journal or Publication Title:	Proceedings of SPIE
Publisher:	SPIE
Refereed:	Yes
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads