This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any probabilistic Turing machine (PTM). Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.

通过研究基于递归神经网络的语言模型（LMs）的计算表达能力，本文通过扩展图灵完备性结果到概率情况，展示了有理加权RLM在无界计算时间下可以模拟任何概率图灵机。相反，在实时计算限制下，这些模型可以模拟确定性的实时有理PTM。

关于循环神经网络语言模型的表示能力