In theoretical neuroscience, understanding the computational and dynamical capabilities of biological neural networks is an issue of central importance. In this context, much interest has been focused on comparing the computational powers of diverse theoretical neural models with those of abstract computing devices.

This comparative approach was initiated by McCulloch and Pitts who proposed a modelisation of the nervous system as a finite interconnection of threshold logic units [19]. For the first time, neural networks were considered as discrete abstract machines, and the issue of their computational capabilities investigated from the automata-theoretic perspective. In this context, Kleene and Minsky proved that recurrent neural networks made up of threshold activation units were computationally equivalent to classical finite state automata [13, 20].

Besides, in a seminal report entitled “Intelligent Machinery” [31], Turing brilliantly introduced many concepts which have later become central in the field of neural computation. For instance, Turing foresaw the possibility of surpassing the capabilities of finite state machines and reaching Turing universality via neural networks called “B-type unorganised machines”. The networks consisted of a general interconnection of NAND neurons, and the consideration of infinitely many such cells could simulate the behaviour of a Turing machine. Moreover, Turing also introduced the key idea of “training” neural networks by considering the possibility of modifying the synaptic connections between the cells by means of what he called “connection-modifiers”. Later, the Turing universality of infinite or heterogeneous neural networks has further been investigated in many directions, see for instance [8, 9, 11, 23]. These seminal works opened up the way to the theoretical computer scientist approach to neural computation. However, the purely discrete and mechanical approach under consideration quickly appeared too restrictive, far from the biological reality.

According to these considerations, von Neumann proposed another relevant approach to the issue of information processing in the brain from the hybrid perspective of digital and analog computation [22]. He considered that the non-linear character of the operations of the brain emerges from a combination of discrete and continuous mechanisms, and therefore envisioned neural computation as something strictly more powerful than abstract machines. Almost in the same time, Rosenblatt proposed the so-called “perceptron” as a more general computational neural model than the McCulloch-Pitts units [24]. The essential innovation consisted in the introduction of numerical synaptic weights and as well as a special interconnection pattern. This neural model gave rise to an algorithmic conception of “learning” achieved by adjusting the synaptic weights of the networks according to some specific task to be completed. This study is nowadays considered as foundational for the field of machine learning. The computational capabilities of the perceptron were further studied by Minsky and Papert [21].

Later, Siegelmann and Sontag made two significant steps forward concerning the precise issue of the computational power of recurrent neural networks. Firstly, they focused their attention on the consideration of more realistic activation functions for the neurons and showed that by extending the activation functions of the cells from boolean to linear-sigmoid, the computational power of the neural networks would drastically increase from finite state automata up to Turing capabilities [28]. The Turing universality of neural networks was then generalised to a broader class of sigmoidal activation functions [12]. The computational equivalence between the so-called rational recurrent neural networks and the Turing machines has nowadays become standard result in the field.

Secondly and most importantly, following von Neumann considerations, they assumed that the variables appearing in the underlying chemical and physical phenomena could be modelled by continuous rather than discrete numbers, and therefore proposed a precise study of the computational power of recurrent neural networks from the perspective of analog computation [27]. They introduced the concept of an analog recurrent neural network as a classical linear-sigmoid neural net equipped with real- instead of rational-weighted synaptic connections. This analog information processing model turns out to be capable of capturing the non-linear dynamical properties that are most relevant to brain dynamics, such as rich chaotic behaviours [7, 25, 26, 29, 32]. In this context, they proved that analog recurrent neural networks are computationally equivalent to Turing machine with advice, hence capable of super-Turing computational capabilities from polynomial time of computation already. They further formulated the so-called Thesis of Analog Computation – an analogous to the Church-Turing thesis, but in the realm of analog computation – stating that no reasonable abstract analog device can be more powerful than first-order analog recurrent neural networks [26, 27].