Abstract

Digital computing algorithms are analyzed using a simple and abstract model for computation: the Turing Machine, or close equivalents. The simplicity of the model makes it possible to measure complexity in terms of only two resources — time and space, and allows us to use asymptotics without concern for noise or the breakdown of physical laws. Analyzing the complexity of analog computation is more difficult because of the modeling problem, and the theory and technique are at an earlier stage of development. In this talk we will discuss this theory, and give some examples of its application. Much of the discussion is based on [1].

© 1987 Optical Society of America