On the Computational Power of RNNs
  Recent neural network architectures such as the basic recurrent neural
network (RNN) and Gated Recurrent Unit (GRU) have gained prominence as
end-to-end learning architectures for natural language processing tasks. But
what is the computational power of such systems? We prove that finite precision
RNNs with one hidden layer and ReLU activation and finite precision GRUs are
exactly as computationally powerful as deterministic finite automata. Allowing
arbitrary precision, we prove that RNNs with one hidden layer and ReLU
activation are at least as computationally powerful as pushdown automata. If we
also allow infinite precision, infinite edge weights, and nonlinear output
activation functions, we prove that GRUs are at least as computationally
powerful as pushdown automata. All results are shown constructively.
