Share Email Print

Proceedings Paper

Continuous-space model of computation is Turing universal
Author(s): Thomas J. Naughton
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 17 November 2000
PDF: 8 pages
Proc. SPIE 4109, Critical Technologies for the Future of Computing, (17 November 2000); doi: 10.1117/12.409212
Show Author Affiliations
Thomas J. Naughton, National Univ. of Ireland/Maynooth (Ireland)

Published in SPIE Proceedings Vol. 4109:
Critical Technologies for the Future of Computing
Sunny Bains; Leo J. Irakliotis, Editor(s)

© SPIE. Terms of Use
Back to Top