Recursion theory on the reals and continuous-time computation

被引:104
作者
Moore, C
机构
[1] Santa Fe Institute, Santa Fe, NM 87501
关键词
D O I
10.1016/0304-3975(95)00248-0
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We define a class of recursive functions on the reals analogous to the classical recursive functions on the natural numbers, corresponding to a conceptual analog computer that operates in continuous time. This class turns out to be surprisingly large, and includes many functions which are uncomputable in the traditional sense. We stratify this class of functions into a hierarchy, according to the number of uses of the zero-finding operator mu. At the lowest level are continuous functions that are differentially algebraic, and computable by Shannon's general purpose analog computer. At higher levels are increasingly discontinuous and complex functions. We relate this mu-hierarchy to the arithmetical and analytical hierarchies of classical recursion theory.
引用
收藏
页码:23 / 44
页数:22
相关论文
共 18 条
[1]   ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS - NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES [J].
BLUM, L ;
SHUB, M ;
SMALE, S .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 21 (01) :1-46
[2]  
COSNARD M, 1994, THEORET COMPUT SCI, V132, P113
[3]  
GRADEL E, NCTR95040 NEUR
[4]  
Kuratowski K, 1966, TOPOLOGY, VI
[5]   A DIFFERENTIALLY ALGEBRAIC REPLACEMENT THEOREM, AND ANALOG COMPUTABILITY [J].
LIPSHITZ, L ;
RUBEL, LA .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1987, 99 (02) :367-372
[6]  
Meer K., 1993, Journal of Complexity, V9, P366, DOI 10.1006/jcom.1993.1023
[7]  
Meer K., 1992, Journal of Complexity, V8, P451, DOI 10.1016/0885-064X(92)90007-X
[8]  
Minsky M. L., 1967, COMPUTATION FINITE I
[9]   GENERALIZED SHIFTS - UNPREDICTABILITY AND UNDECIDABILITY IN DYNAMIC-SYSTEMS [J].
MOORE, C .
NONLINEARITY, 1991, 4 (02) :199-230
[10]   UNPREDICTABILITY AND UNDECIDABILITY IN DYNAMIC-SYSTEMS [J].
MOORE, C .
PHYSICAL REVIEW LETTERS, 1990, 64 (20) :2354-2357