Turing Completeness of Artificial Neural Networks

Some artificial neural networks (ANNs), like recurrent neural networks (RNNs), have long been proved to be Turing complete. Yet looking into the proofs reveals that nearly all proofs required the model to have unbounded numerical precision and resources, an ideal condition that is never possible in reality. It was proven that ANNs with realistically limited numerical precision and resources degrade into much smaller complexity classes. More recent works show that Turing completeness could nonetheless be recovered when bounded precision is paired with another unbounded resource. All these results determine how to interpret the upper limit of ANN models' computation capability. This review look into the Turing completeness of RNNs and modern transformer chronologically. Both architecture followed the same history in universality proofs: Turing complete in ideal -- small complexity class in reality -- partial or full universality recovery with lifted precision or resource bounds. We thus argue that a precision and resource aware view of universality, one that always pairs claims of universality with the resource assumptions they require, is the right frame for interpreting claims about what ANNs can and cannot compute.