Part of Advances in Neural Information Processing Systems 14 (NIPS 2001)
Recurrent neural networks of analog units are computers for real(cid:173) valued functions. We study the time complexity of real computa(cid:173) tion in general recurrent neural networks. These have sigmoidal, linear, and product units of unlimited order as nodes and no re(cid:173) strictions on the weights. For networks operating in discrete time, we exhibit a family of functions with arbitrarily high complexity, and we derive almost tight bounds on the time required to compute these functions. Thus, evidence is given of the computational lim(cid:173) itations that time-bounded analog recurrent neural networks are subject to.