Computational capabilities of recurrent NARX neural networks

Hava T. Siegelmann, Bill G. Horne, C. Lee Giles

Research output: Contribution to journalArticlepeer-review

364 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)208-215
Number of pages8
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Issue number2
StatePublished - 1997

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Computational capabilities of recurrent NARX neural networks'. Together they form a unique fingerprint.

Cite this