Artificial neural networks (ANNs) with recurrence and self-attention have been shown to be Turing-complete (TC). However, existing work has shown that these ANNs require multiple turns or unbounded computation time, even with unbounded precision in weights, in order to recognize TC grammars. However, under constraints such as fixed or bounded precision neurons and time, ANNs without memory are shown to struggle to recognize even context-free languages. In this work, we extend the theoretical foundation for the $2^{nd}$-order recurrent network ($2^{nd}$ RNN) and prove there exists a class of a $2^{nd}$ RNN that is Turing-complete with bounded time. This model is capable of directly encoding a transition table into its recurrent weights, enabling bounded time computation and is interpretable by design. We also demonstrate that $2$nd order RNNs, without memory, under bounded weights and time constraints, outperform modern-day models such as vanilla RNNs and gated recurrent units in recognizing regular grammars. We provide an upper bound and a stability analysis on the maximum number of neurons required by $2$nd order RNNs to recognize any class of regular grammar. Extensive experiments on the Tomita grammars support our findings, demonstrating the importance of tensor connections in crafting computationally efficient RNNs. Finally, we show $2^{nd}$ order RNNs are also interpretable by extraction and can extract state machines with higher success rates as compared to first-order RNNs. Our results extend the theoretical foundations of RNNs and offer promising avenues for future explainable AI research.

这项研究通过扩展第二阶循环神经网络的理论基础，证明存在一类有界时间的第二阶循环神经网络，具备图灵完备性，可以直接将转移表编码到其循环权重中，实现有界时间计算，并通过设计可解释。同时，该研究还展示了在有界权重和时间约束下，没有记忆的第二阶循环神经网络在识别正则语法方面优于传统的循环神经网络和门控循环单元等现代模型，并提供了识别任何一类正则语法所需的最大神经元数量的上界和稳定性分析。大量关于Tomita语法的实验证实了研究结果，并展示了采用第二阶循环神经网络进行解释和提取状态机时的成功率较一阶循环神经网络更高。这些结果拓展了循环神经网络的理论基础，并为未来可解释人工智能的研究提供了有希望的方向。

关于二阶递归神经网络的计算复杂性和形式层次的研究