rnn-theoretical-power-exceeded-practical-utility

IN derived (depth 1)

Created 2026-06-21T10:01:28+00:00 · Reviewed 2026-06-21T15:37:01+00:00

RNNs possess strong theoretical computational power — Turing-completeness with rational weights (Siegelmann & Sontag 1994) and context-sensitive language recognition via LSTM that surpasses what HMM-based models achieve — while their sequential hidden-state processing, which updates state at each time step, represents an inherent constraint on parallelism.

Justifications

SL — Theoretical power beliefs combined with the sequential processing constraint reveal that RNNs were superseded not for lack of expressivity but for lack of parallelizability

Antecedents (all must be IN):

IN rnn-turing-completeness-siegelmann-sontag — Siegelmann & Sontag (1994) proved that recurrent neural networks with rational weights are Turing-complete, and with real-valued weights they are super-Turing.
IN lstm-recognizes-context-sensitive-languages — LSTM can recognize context-sensitive languages, surpassing HMM-based models which are limited to regular languages.
IN rnn-hidden-state-sequential-processing — Recurrent neural networks process sequential data by maintaining a hidden state updated at each time step based on current input and the previous hidden state, enabling temporal dependency capture.

Dependents

These beliefs depend on this one:

OUT rnn-theoretical-power-practically-accessible — RNNs' theoretical computational power (Turing-completeness, context-sensitive language recognition) is practically accessible for sequence modeling tasks, given LSTM's ability to learn over thousands of timesteps.