  While Recurrent Neural Networks (RNNs) are famously known to be Turing
complete, this relies on infinite precision in the states and unbounded
computation time. We consider the case of RNNs with finite precision whose
computation time is linear in the input length. Under these limitations, we
show that different RNN variants have different computational power. In
particular, we show that the LSTM and the Elman-RNN with ReLU activation are
strictly stronger than the RNN with a squashing activation and the GRU. This is
achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We
show empirically that the LSTM does indeed learn to effectively use the
counting mechanism.
