Turing universal neural networks do not require global clocks.

Abstract

Recurrent neural networks were proven to be Turing universal in the 1990s, motivating computational complexity studies of spiking networks, neural Turing machines with differentiable activations, and transformers. At the time, neural networks were exploratory and small, whereas today large-scale deployment makes energy efficiency critical. We thus extend the development of computational foundations of neural networks to asynchronous networks. Asynchrony is modeled by updating a single randomly selected neuron per step, eliminating global updates and reducing energy use. While asynchrony introduces variability in update sequences and thus has often been considered impractical for computing, we introduce design constraints which lead to Turing universal asynchronous architectures. We prove universality both for asynchronous fixed architectures with varying-precision neurons and for variable architectures with fixed-precision neurons. These results advance the theoretical understanding of asynchronous networks, suggesting that they preserve full computational power, remain amenable for efficient training, and may achieve substantial reductions in energy use.