Computational capabilities of
recurrent NARX neural networksy

Hava T. Siegelmann
Department of Information Systems Engineering
Faculty of Industrial Engineering and Management
Technion (Israel Institute of Technology)
Haifa 32000, Israel
Email: iehava@ie.technion.ac.il

Bill G. Horne and C. Lee Giles?
NEC Research Institute
4 Independence Way
Princeton, NJ 08540
Email: fhorne,gilesg@research.nj.nec.com

? Also with
UMIACS
University of Maryland
College Park, MD 20742

Abstract
Recently, fully connected recurrent neural networks have been proven to be computationally rich | at least as powerful as Turing machines. This work focuses on another network which is popular in control applications and has been found to be very effective at learning a variety of problems. These networks are based upon Nonlinear AutoRegressive models with eXogenous Inputs (NARX models), and are therefore called NARX networks. As opposed to other recurrent networks, NARX networks have a limited feedback which comes only from the output neuron rather than from hidden states. They are formalized by
y(t) = ?
?
u(t ? nu); : : : ; u(t ? 1); u(t); y(t ? ny); : : : ; y(t ? 1)
?
;
where u(t) and y(t) represent input and output of the network at time t, nu and ny are the input and output order, and the function ? is the mapping performed by a Multilayer Perceptron. We constructively prove that the NARX networks with a finite number of parameters are computationally as strong as fully connected recurrent networks and thus Turing machines. We conclude that in theory one can use the NARX models, rather than conventional recurrent networks without any computational loss even though their feedback is limited. Furthermore, these results raise the issue of what amount of feedback or recurrence is necessary for any network to be Turing equivalent and what restrictions on feedback limit computational power.

yPublished in IEEE Transactions on Systems, Man and Cybernetics{Part B: Cybernetics, 27(2), p. 208, 1997.