Resource-bounded Continuity and Sequentiality for Type-two Functionals (Extended Abstract)
Samuel R. Buss, Bruce M. Kapron · 1991
) Samuel R. Buss Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112 [email protected] Bruce M. Kapron y Computer Science Department University of Victoria Victoria BC CANADA V8W 3P6 [email protected] Abstract We define notions of resource-bounded continuity and sequentiality for type-two functionals with total inputs, and prove that in the resource-bounded model there are continuous functionals which cannot be efficiently simulated by sequential functionals. We also show that for some naturallydefined classes of continuous functionals, an efficient simulation is possible. 1. Introduction The notion of continuity has long played an important role in higher-type computability theory, as well as in the theory of programming languages. A central theme in this area is the relationship between continuity and sequentiality. Continuity can be seen as a proper generalization of sequentiality, although there are certain special cases for which ...