Turing complete neural computation based on synaptic plasticity

Summary

In neural computation, the essential information is generally encoded into the neurons via their spiking configurations, activation values or (attractor) dynamics. The synapses and their associated plasticity mechanisms are, by contrast, mainly used to process this information and implement the crucial learning features. Here, we propose a novel Turing complete paradigm of neural computation where the essential information is encoded into discrete synaptic states, and the updating of this information achieved via synaptic plasticity mechanisms. More specifically, we prove that any 2-counter machine—and hence any Turing machine—can be simulated by a rational-weighted recurrent neural network employing spike-timing-dependent plasticity (STDP) rules. The computational states and counter values of the machine are encoded into discrete synaptic strengths. The transitions between those synaptic weights are then achieved via STDP. These considerations show that a Turing complete synaptic-based paradigm of neural computation is theoretically possible and potentially exploitable. They support the idea that synapses are not only crucially involved in information processing and learning features, but also in the encoding of essential information. This approach represents a paradigm shift in the field of neural computation.

Keywords:

Neurons – Synapses – Machine learning algorithms – Action potentials – Recurrent neural networks – Language – Synaptic plasticity – Neural pathways

Introduction

How does the brain compute? How do biological neural networks encode and process information? What are the computational capabilities of neural networks? Can neural networks implement abstract models of computation? Understanding the computational and dynamical capabilities of neural systems is a crucial issue with significant implications in computational and system neuroscience, artificial intelligence, machine learning, bio-inspired computing, robotics, but also theoretical computer science and philosophy.

In 1943, McCulloch and Pitts proposed the concept of an artificial neural network (ANN) as an interconnection of neuron-like logical units [1]. This computational model significantly contributed to the development of two research directions: (1) Neural Computation, which studies the processing and coding of information as well as as the computational capabilities of various kinds of artificial and biological neural models; (2) Machine Learning, which concerns the development and utilization of neural network algorithms in Artificial Intelligence (AI).

The proposed study lies within the first of these two approaches. In this context, the computational capabilities of diverse kinds of neural networks have been shown to range from the finite automaton degree [1–3] up to the Turing [4] or even to the super-Turing levels [5–7] (see [8] for a survey of complexity theoretic results). In short, Boolean recurrent neural networks are computationally equivalent fo finite state automata; analog neural networks with rational synaptic weights are Turing complete; and analog neural nets with real synaptic weights as well as evolving neural nets are capable of super-Turing capabilities (cf. Table 1). These theoretical results have later been improved, motivated by the possibility to implement finite state machines on electronic hardwares (see for instance [9–13]). Around the same time, the computational power of spiking neural networks (instead of sigmoidal ones) has also been extensively studied [14, 15]. More recently, the study of P systems—parallel abstract models of computation inspired from the membrane structure of biological cells—has become a highly active field of research [16–18].

Concerning the second direction, Turing himself brilliantly anticipated the two concepts of learning and training that would later become central to machine learning [36]. These ideas were realized with the introduction of the perceptron [37], which gave rise to the algorithmic conception of learning [38–40]. Despite some early limitation issues [41], the development of artificial neural networks has steadily progressed since then. Nowadays, artificial neural networks represent a most powerful class of algorithms in machine learning, thanks to their highly efficient training capabilities. In particular, deep learning methods—multilayer neural networks that can learn in supervised and/or unsupervised manners—have achieved impressive results in numerous different areas (see [42] for a brilliant survey and the references therein).

These approaches share a common and certainly sensible conception of neural computation that could be qualified as a neuron-based computational framework. According to this conception, the essential information is encoded into the neurons, via their spiking configurations, activation values or (attractor) dynamics. The synapses and their associated plasticity mechanisms are, by contrast, essentially used to process this information and implement the crucial learning features. For instance, in the simulation of abstract machines by neural networks, the computational states of the machines are encoded into activation values or spiking patterns of neurons [8]. Similarly, in most if not all deep learning algorithms, the input, output and intermediate information is encoded into activation values of input, output and hidden (layers of) neurons, respectively [42]. But what if the synaptic states would also play a crucial role in the encoding of information? What if the role of the synapses would not only be confined to the processing of information and learning processes, as crucial as these features might be? In short, what about a synaptic-based computational framework?

In biology, the various mechanisms of synaptic plasticity provide “the basis for most models of learning, memory and development in neural circuits” [43]. Spike-timing-dependent plasticity (STDP) refers to the biological Hebbian-like learning process according to which the synapses’ strengths are adjusted based on the relative timings of the presynaptic and postsynaptic spikes [38, 44, 45]. It is widely believed that STDP “underlies several learning and information storage processes in the brain, as well as the development and refinement of neuronal circuits during brain development” (see [46] and the references therein). In particular, fundamental neuronal structures like synfire chains [47–51] (pools of successive layers of neurons strongly connected from one stratum to the next by excitatory connections), synfire rings [52] (looping synfire chains) and polychronous groups [53] (groups of neurons capable of generating time-locked reproducible spike-timing patterns), have all been observed to emerge in self-organizing neural networks employing various STDP mechanisms [52–55]. On another level, regarding STDP mechnisms, it has been shown that synapses might change their strengths by jumping between discrete mechanistic states, rather than by simply moving up and down in a continuum of efficacy [56].

Based on these considerations, we propose a novel Turing complete synaptic-based paradigm of neural computation. In this framework, the essential information is encoded into discrete synaptic states instead of neuronal spiking patterns, activation values or dynamics. The updating of this information is then achieved via synaptic plasticity mechanisms. More specifically, we prove that any 2-counter machine—and hence any Turing machine—can be simulated by a rational-weighted recurrent neural network subjected to STDP. The computational states and counter values of the machine are encoded into discrete synaptic strengths. The transitions between those synaptic weights are achieved via STDP. These results show that a Turing complete synaptic-based paradigm of computation is theoretically possible and potentially exploitable. They support the idea that synapses are not only crucially involved in information processing and learning features, but also in the encoding of essential information in the brain. This approach represents a paradigm shift in the field of neural computation.

The possible impacts of these results are both practical and theoretical. In the field of neuromorphic computing, our synaptic-based paradigm of neural computation might lead to the realization of novel analog neuronal computers implemented on VLSI technologies. Regarding AI, our approach might lead to the development of new machine learning algorithms. On a conceptual level, the study of neuro-inspired paradigms of abstract computation might improve the understanding of both biological and artificial intelligences. These aspects are discussed in the conclusion.

Materials and methods

Recurrent neural networks

A rational-weighted recurrent neural network (RNN) N consists of a synchronous network of neurons connected together in a general architecture. The network is composed of M input neurons ( u i ) i = 1 M and N internal neurons ( x i ) i = 1 N. The dynamics of network N is computed as follows: given the activation values of the input neurons ( u j ( t ) ) j = 1 M and internal neurons ( x j ( t ) ) j = 1 N at time step t, the activation values of the internal neurons ( x i ( t + 1 ) ) i = 1 N at time step t + 1 are given by the following equations:

where a i j ( t ) , b i j ( t ) ∈ Q are the rational weights of the synaptic connections from x_j to x_i and u_j to x_i at time t, respectively, c i ( t ) ∈ Q is the rational bias of cell x_i at time t, and f is either the hard-threshold activation function θ or the linear sigmoid activation function σ defined by

A neuron is called Boolean or analog depending on whether its activation value is computed by the function θ or σ, respectively. Input neurons ( u i ) i = 1 M are all Boolean.

The input state and internal state of N at time t are the vectors

For any Boolean input stream u = u(0)u(1)u(2) ⋯, the computation of N over input u is the sequence of internal states N ( u ) = x ( 0 ) x ( 1 ) x ( 2 ) …, where x(0) = 0 and the components of x(t) are given by Eq (1), for each t > 0. A simple recurrent neural network is illustrated in Fig 1.

A spike-timing dependent plasticity (STDP) rule modifies the synaptic weights a_ij(t) according to the spiking patterns of the presynaptic and postsynaptic cells x_j and x_i [45]. Here, we consider two STDP rules. The first one is a classical generalized Hebbian rule [38]. It allows the synaptic weights to vary across finitely many values comprised between two bounds a_min and a_max (0 < a_min < a_max < 1). The rule is given as follows:

where ⌊x⌋ denotes the floor of x (the greatest integer less than or equal to x) and η > 0 is the learning rate. Accordingly, the synaptic weight a_ij(t) is incremented (resp. decremented) by η at time t + 1 if the presynaptic cell x_j spikes 1 time step before (resp. after) the postsynaptic cell x_i. The floor function is used to truncate the activation values of analog neurons to their integer part, if needed. The synaptic weights enabled by this rule is illustrated in Fig 2. In the sequel, this STDP rule will be used to encode the transitions between the finitely many computational states of the machine to be simulated.

The second rule is an adaptation to our context of a classical Hebbian rule. It allows the synaptic weights to vary across the infinitely many values of the sequence

The rule is given as follows:

As for the previous one, the synaptic weight a_ij(t) is incremented (resp. decremented) at time t+1 if the presynaptic cell x_j spikes 1 time step before (resp. after) the postsynaptic cell x_i. But in this case, the synaptic weight varies across the infinitely many successive values of the sequence β. For instance, if a i j ( t ) = 1 2 + 1 4 + 1 8 = 0 . 875 is incremented (resp. decremented) by the STDP rule, then a i j ( t + 1 ) = 1 2 + 1 4 + 1 8 + 1 16 = 0 . 9375 (resp. a i j ( t + 1 ) = 1 2 + 1 4 = 0 . 75). Here, the floor functions are removed, since this rule will only be applied to synaptic connections between Boolean neurons. The synaptic weights enabled by this rule is illustrated in Fig 2. In the sequel, this STDP rule will be used to encode the variations among the infinitely many possible counter values of the machine to be simulated.

Finite state automata

A deterministic finite state automaton (FSA) is a tuple A = ( Q , Σ , δ , q 0 , F ), where:

• Q = {q₀, …, q_n−1} is a finite set of computational states;

• Σ is an alphabet of input symbols;

• δ: Q × Σ → Q is a transition function;

• q₀ ∈ Q is the initial state;

• F ⊆ Q is the set of final states.

Each transition δ(q, a) = q′ signifies that if the automaton is state q ∈ Q and reads input symbol a ∈ Σ, then it will move to state q′ ∈ Q. For any input w = a₀a₁ ⋯a_p ∈ Σ*, the computation of A over w is the finite sequence

such that q i 0 = q 0 and δ ( q i k , a k ) = q i k + 1, for all k = 0, …, p. Such a computation is usually denoted as

Input w is said to be accepted (resp. rejected) by automaton A if the last state q i p + 1 of computation A ( w ) belongs (resp. does not belong) to the set of final states F. The set of all inputs accepted by A is the language recognized by A. Finite state automata recognize the class of regular languages. A finite state automaton is generally represented as a directed graph, as illustrated in Fig 3.

Counter machines

A counter machine is a finite state automaton provided with additional counters [57]. The counters are used to store integers. They can be pushed (incremented by 1), popped (decremented by 1) or kept unchanged. At each step, the machine determines its next computational state according to its current input symbol, computational state and counters’ states, i.e., if counters are zero or non-zero.

Formally, a deterministic k-counter machine (CM) is a tuple C k = ( Q , Σ , C , O , δ , q 0 , F ), where:

• Q = {q₀, …, q_n−1} is a finite set of computational states;

• Σ is an alphabet of input symbols not containing the empty symbol ϵ (recall that the empty symbol satisfies ϵw = wϵ = w, for any string w ∈ Σ*);

• C = {⊥, ⊤} is the set of counter states, where ⊥, ⊤ represent the zero and non-zero states, respectively;

• N is the set of counter values (doesn’t need to be hold in the tuple C k);

• O = {push, pop, −} is the set of counter operations;

• δ: Q × Σ ∪ {ϵ} × C^k → Q × O^k is a (partial) transition function;

• q₀ ∈ Q is the initial state;

• F ⊆ Q is the set of final states.

The value and state of counter j are denoted by c_j and c ¯ j, respectively, for j = 1, …, k. (In the sequel, certain cells will also be denoted by c_j’s and c ¯ j’s. The use of same notations to designate counter’s values or states and specific cells will be clear from the context.) The “bar function” (c ↦ c ¯) retrieves the counter’s state from its value. It is naturally defined by c ¯ j = ⊥ if c_j = 0 and c ¯ j = ⊤ if c_j > 0. The value of counter j after application of operation o_j ∈ O is denoted by o_j(c_j). The counter operations influence their values in the following natural way:

• If o_j = push, then o_j(c_j) = c_j + 1;

• If o_j = pop, then o_j(c_j) = max(c_j − 1, 0);

• If o_j = −, then o_j(c_j) = c_j.

Each transition δ ( q , a , c ¯ 1 , … , c ¯ k ) = ( q ′ , o 1 , … , o k ) signifies that if the machine is state q ∈ Q, reads the regular or empty input symbol a ∈ Σ ∪ {ϵ} and has its k counter being in states c ¯ 1 , … , c ¯ k ∈ C, then it will move to state q′ ∈ Q and perform the k counter operations o₁, …, o_k ∈ O. Depending on whether a ∈ Σ or a = ϵ, the corresponding transition is called a regular transition or an ϵ-transition, respectively. We assume that δ is a partial (rather than a total) function. Importantly, the determinism is expressed by the fact that the machine can never face a choice between either a regular or an ϵ-transition, i.e., for any q ∈ Q, any a ∈ Σ and any c ¯ 1 , … , c ¯ k ∈ C, if δ ( q , a , c ¯ 1 , … , c ¯ k ) is defined, then δ ( q , ϵ , c ¯ 1 , … , c ¯ k ) is undefined [57].

For any input w = a₀a₁ ⋯ a_p ∈ Σ*, the computation of a k-counter machine C k over input w can be described as follows. For each successive input symbol a_i ∈ Σ, before trying to process a_i, the machine first tests if an ϵ-transition is possible. If this is the case, it performs this transition. Otherwise, it tests if the regular transition associated with a_i is possible, and if so, performs it. The deterministic condition ensures that a regular and an ϵ-transition are never possible at the same time. When no more transition can be performed, the machine stops.

For any input w = a₀a₁ ⋯ a_p ∈ Σ*, the computation of C k over w is the unique finite or infinite sequence of states, symbols and counter values encountered by C k while reading the successive bits of w possibly interspersed with ϵ symbols. The formal definition involves the following notions.

An instantaneous description of C k is a tuple ( q , w , c 1 , … , c k ) ∈ Q × Σ * × N k. For any empty or non-empty symbol a′ ∈ Σ ∪ {ϵ} and any w ∈ Σ*, the relation “⊢” over the set of instantaneous descriptions is defined as follows:

Note that depending on whether a′ = ϵ or a′ ∈ Σ, the relation “⊢” is determined by an ϵ-transition or a regular transition, respectively. (Note also that when a′ = ϵ, one has a′w = ϵw = w, and in this case, the relation “⊢” keeps w unchanged).

For any input w = a₀a₁ ⋯ a_p ∈ Σ*, the determinism of C k ensures that there is a unique finite or infinite sequence of instantaneous descriptions

such that ( q n 0 , w 0 , c 1 , 0 , … , c k , 0 ) = ( q 0 , w , 0 , … , 0 ) is the initial instantaneous description, and ( q n i , w i , c 1 , i , … , c k , i ) ⊢ ( q n i + 1 , w i + 1 , c 1 , i + 1 , … , c k , i + 1 ), for all i < l. Then, the computation of C k over w, denoted by C k ( w ), is the finite or infinite sequence defined by

where a i ′ = ϵ if w_i = w_i+1 (case of an ϵ-transition), and a i ′ is the first bit of w_i otherwise (case of a regular transition), for all i < l. Note that the computation over w can take longer than |w| = p + 1 steps, even be infinite, due to the use of ϵ-transitions. The input w ∈ Σ* is said to be accepted by C k if the computation of the machine over w is finite, consumes all letters of w and stops in a state of F, i.e., if a l ′ = ϵ and q n l ∈ F. It is rejected otherwise. The set of all inputs accepted by C k is the language recognized by C k.

It is known that 1-counter machines are strictly more powerful than finite state automata, and k-counter machines are computationally equivalent to Turing machines (Turing complete), for any k ≥ 2 [57]. However, the class of k-counter machines that do not make use of ϵ-transitions is not Turing complete. For this reason, the simulation of ϵ-transitions by our neural networks will be essential towards the achievement of Turing-completeness.

A k-counter machine can also be represented as a directed graph, as illustrated in Fig 4. The 2-counter machine of Fig 4 recognizes a language that is recursively enumerable but not context-free, i.e., it can be recognized by some Turing machine, yet by no pushdown automaton. Note that this 2-counter machine contains ϵ-transitions.

Results

We show that any k-counter machine can be simulated by a recurrent neural network composed of Boolean and analog neurons, and using the two STDP rules described by Eqs (2) and (3). In this computational paradigm, the states and counter values of the machine are encoded into specific synaptic weights of the network. The transitions between those states and counter values are reflected by an evolution of the corresponding synaptic weights. Since 2-counter machines are computationally equivalent to Turing machines, these results show that the proposed STDP-based recurrent neural networks are Turing complete.

Construction

We provide an algorithmic construction which takes the description of a k-counter machine C k as input and provides a recurrent neural network N that simulates C k as output. The network N is constructed by assembling several modules together: an input encoding module, an input transmission module, a state module, k counter modules and several detection modules. These modules are described in detail in the sequel. The global behaviour of N can be summarized as follows.

• The computational state and k counter values of C k are encoded into specific synaptic weights belonging to the state module and counter modules of N, respectively.

• At the beginning of the simulation, N receives its input stream via successive activations of its input cells belonging to the input encoding module. Meanwhile, this module encodes the whole input stream into a single rational number, and stores this number into the activation value of a sigmoid neuron.

• Then, each time the so-called tic cell of the input encoding module is activated, N triggers the simulation of one computational step of C k.

  • First, it attempts to simulate an ϵ-transition of C k by activating the cell u_ϵ of the input transmission module. If such a transition is possible in C k, then N simulates it.

  • Otherwise, a signal is sent back the input encoding module. This module then retrieves the last input bit a stored in its memory, and attempts to simulate the regular transition of C k associated with a by activating the cell u_a of the input transmission module. If such a transition is possible in C k, then N simulates it.

• The network N simulates a transition of C k as follows: first, it retrieves the current computational state and k counter values of C k encoded into k + 1 synaptic weights by means of its detection modules. Based on this information, it sends specific signals to the state module and counter modules. These signals update specific synaptic weights of these modules in such a way to encode the new computational state and counter values of C k.

The general architecture of N is illustrated in Fig 5. The general functionalities of the modules are summarized in Table 2. The following sections are devoted to the detailed description of the modules, as well as to the proof of correctness of the construction.

Stack encoding

In the sequel, each binary input stream will be piled up into a “binary stack”. In this way, the input stream can be stored by the network, and then processed bit by bit at successive time steps interspersed by constant intervals. The construction of the stack is achieved by “pushing” the successive incoming bits into it. The stack is encoded as a rational number stored in the activation value of one (or several) analog neurons. The pushing and popping stack operations can be simulated by simple analog neural circuits [4]. We now present these notions in detail.

A binary stack whose elements from top to bottom are γ₁, γ₂, …, γ_p ∈ {0, 1} is represented by the finite string γ = γ₁γ₂ ⋯ γ_p ∈ {0, 1}*. The stack γ whose top element has been popped is denoted by pop(γ) = γ₂ ⋯ γ_p, and the stack obtained by pushing element α ∈ {0, 1} into γ is denoted by push(α, γ) = αγ₁ γ₂ … γ_p (α is now the top element). For instance, if γ = 0110, then pop(γ) = 110, push(0, γ) = 00110 and push(1, γ) = 10110.

In our context, any stack γ = γ₁γ₂ ⋯ γ_p ∈ {0, 1}* is encoded by the rational number r ¯ γ ≔ ∑ i = 1 n 2 γ i + 1 4 i ∈ [ 0 , 1 ] [4]. Hence, the top element γ₁ of γ can be retrieved by the operation t o p ( γ ) = σ ( 4 r ¯ γ - 2 ) ∈ { 0 , 1 }, where σ is the linear sigmoid function defined previously. The encodings of push(0, γ) and push(1, γ) are given by σ ( r ¯ γ 4 + 1 4 ) and σ ( r ¯ γ 4 + 3 4 ), respectively. The encoding of pop(γ) is given by σ ( 4 r ¯ γ - 2 t o p ( γ ) - 1 ). As an illustration, the stack γ = 0110 is encoded by r ¯ γ = 1 4 + 3 16 + 3 64 + 1 256. The top element of γ is t o p ( γ ) = σ ( 1 + 3 4 + 3 16 + 1 64 - 2 ) = 0. The encodings of push(0, γ) and push(1, γ) are 1 4 + 1 16 + 3 64 + 3 256 + 1 1024 and 3 4 + 1 16 + 3 64 + 3 256 + 1 1024, which represents the stacks 00110 and 10110, respectively. The encoding of pop(γ) is σ ( 1 + 3 4 + 3 16 + 1 64 - 2 · 0 - 1 ) = 3 4 + 3 16 + 1 64, which represents to the stack 110. These four operations can be implemented by simple neural circuits.

Input encoding module

The input encoding module is used for two purposes: pile up the successive input bits into a stack, and implement a “tic mechanism” which triggers the simulation of one computational step of the counter machine by the network. These two processes are described in detail below. This module (the most intricate one) has been designed on the basis of the previous considerations about stack encoding, involving neural circuits that implement the “pop”, “top” and “pop” operations. It is composed of 31 cells in₀, in₁, end, tic, c₁, …, c₂₀, d₁, …, d₇, some of which being Boolean and others analog, as illustrated in Fig 6. It is connected to the input transmission module and the detection modules described below.

The three Boolean cells in₀, in₁ and end are input cells of the network. They are used to transmit the successive inputs bits to the network. The transmission of input 0 or 1 is represented by a spike of cell in₀ or in₁, respectively. At the end of the input stream, cell end spikes to indicate that all inputs have been processed.

The activity of this module, illustrated in Fig 7, can be described as follows. Suppose that the input stream a₁ ⋯ a_p is transmitted to the network. While the bits a₁, …, a_p are being received, the module builds the stack γ = a₁ ⋯ a_p, and stores its encoding r ¯ γ into the activation values of an analog neuron. To achieve this, the module first pushes every incoming input a_i into a stack γ′ (first ‘push’ circuit in Fig 6). Since pushed elements are by definition added on the top of the stack, γ′ consists of elements a₁, …, a_p in reverse order, i.e., γ′ = a_p ⋯ a₁. The encoding r ¯ γ ′ of stack γ′ is stored in cell c₁. Then, the module pops the elements of γ′ from top to bottom (first ‘pop’ circuit in Fig 6), and pushed them into another stack γ (second ‘push’ circuit in Fig 6). After completion of this process, γ consists of elements a₁, …, a_p in the right order, i.e., γ = a₁ ⋯ a_p. The encoding r ¯ γ of stack γ is stored in cell c₁₄.

The Boolean cell tic is also an input cell. Each activation this cell triggers the simulation of one computational step of the counter machine by the network. When the tic cell spikes, it sends a signal to cell u_ϵ of the next input transmission module. The activation of u_ϵ attempts to launch the simulation of an ϵ-transition of the machine. If, according to the current computational and counter states of the machine, an ϵ-transition is possible, then the network simulates it via its other modules, and at the same time, sends an inhibitory signal to c₁₅. Otherwise, after some delay (‘delays’ circuit in Fig 6), cell c₁₅ is activated. This cell triggers a sub-circuit that pops the current stack γ (second ‘pop’ circuit in Fig 6) and transmits its top element a ∈ {0, 1} to cell u_a of the next input transmission module. Then, the activation of u_a launches the simulation of a regular transition of the machine associated with input symbol a, via the other modules of the network.

The module is composed of several sub-circuits that implement the top(), push() and pop() operations described previously, as shown in Fig 6. An input encoding module is denoted as input_encoding_module().

Input transmission module

The input transmission module is used to transmit to the network the successive input bits sent by the previous input encoding module. The module simply consists of 3 Boolean input cells u₀, u₁, u_ϵ followed by 3 layers of Boolean delay cells, as illustrated in Fig 8. It is connected to the input encoding module described above, and to the state module, counter modules and detection modules described below. The activation of cell u₀, u₁ or u_ϵ simulates the reading of input symbol 0, 1 or ϵ by the counter machine, respectively. Each time such a cell is activated, the information propagates along the delay cells of the corresponding row. An input transmission module is denoted as input_transmission_module().

State module

In our model, the successive computational states of the counter machine are encoded as rational numbers, and stored as successive weights of a designated synapse w_s(t) (subscript s refers to ‘state’). More precisely, the fact that the machine is in state q_k is encoded by the rational weight w_s(t) = a_min + k ⋅ η, for k = 0, …, n − 1, where a_min and η are parameters of the STDP rule given by Eq (2). Hence, the change in computational state of the machine is simulated by incrementing or decrementing w_s(t) in a controlled manner. This process is achieved by letting w_s(t) be subjected to the STDP rule of Eq (2), and by triggering specific spiking patterns of the presynaptic and postsynaptic cells of w_s(t).

The state module is designed to implement these features. It is composed of a Boolean presynaptic cell pre_s connected to an analog postsynaptic cell post_s by a synapse of weight w_s(t), as well as of 6(n − 1) Boolean cells c₁, …, c_{3(n − 1)} and c ¯ 1 , … , c ¯ 3 ( n - 1 ) (for some n to be specified), as illustrated in Fig 9. The synaptic weight w_s(t) is subjected to the STDP rule of Eq (2), and has an initial value of w_s(0) = a_min. The architecture of the module ensures that the activation of cell c_3k+1 or c ¯ 3 k + 1 triggers successive specific spiking patterns of pre_s and post_s which, according to STDP (Eq (2)), increments or decrements w_s(t) by (n − 1 − k) ⋅ η, for any 0 ≤ k ≤ n − 2, respectively (for instance, if k = 0, then w_s(t) is incremented or decremented by (n − 1) ⋅ η, whereas if k = n − 2, then w_s(t) is only incremented or decremented by 1 ⋅ η). The module is linked to the input transmission module described above and to the detection modules described below.

The activity of this module, illustrated in Fig 10, can be described as follows. Suppose that at time step t, one has w_s(t) = v and one wishes to increment (resp. decrement) w_s(t) by (n − 1 − k) ⋅ η, where η is the learning rate of the STDP rule of Eq (2) and 0 ≤ k ≤ n − 2. To achieve this, we activate the cell c_3k+1 (resp. cell c ¯ 3 k + 1) (a blue cell of Fig 9). The activation of c_3k+1 (resp. cell c ¯ 3 k + 1) launches a chain of activations of the next cells (red events in Fig 10), which, according to the connectivity of the module, induces k successive pairs of spikes of pre_s followed by post_s (resp. post_s followed by pre_s) (blue events in Fig 10). Thanks to the STDP rule of Eq (2), these spiking patterns increment (resp. decrement) k times the value of w_s(t) by an amount of η. A state module with 6(n − 1) + 2 cells is denoted as state_module(n − 1).

Counter module

In our model, the successive counter values of the machine are encoded as rational numbers and stored as successive weights of designated synapses w c j ( t ), for j = 1, …, k (subscript c_j refers to ‘counter j’). More precisely, the fact that counter j has a value of n ≥ 0 at time t is encoded by the synaptic weight w c j ( t ) having the rational value r n ≔ ∑ i = 1 n 1 2 i (with the convention that r₀ ≔ 0). Then, the “push” (incrementing the counter by 1) and “pop” (decrementing the counter by 1) operations are simulated by incrementing or decrementing w c j ( t ) appropriately.

The k counter modules are designed to implement these features. Each counter module is composed of 12 Boolean cells push, pop, test, = 0, ≠ 0, pre_c, post_c, c₁, c₂, c₃, c₄, c₅, as illustrated in Fig 11. The presynaptic and postsynaptic cells pre_c and post_c are connected by a synapse of weight w_c(t) subjected to the second STDP rule given by Eq (3) and having an initial value of w_c(0) = 0. Accordingly, the values of w_c(t) may vary across the elements of the infinite sequence β = ( 1 - 1 2 k ) k = 0 ∞ = ( 0 , 0 . 5 , 0 . 75 , 0 . 875 , 0 . 9375 , … ). The module is connected to the input transmission module described above and to detection modules described below.

The activity of this module, illustrated in Fig 12, can be described as follows. Each activation of the push (resp. pop) cell (blue events in Fig 12) propagates into the circuit and results 2 time steps later in successive spikes of the pre_c and post_c cells (resp. post_c and pre_c cells), which, thanks to the STDP rule of Eq (3), increment (resp. decrement) the value of w_c(t) (red curve in Fig 12). The activation of the test cell (blue events in Fig 12) results 4 time steps later in the spike of the Boolean cell ‘= 0’ or ‘≠ 0’ (red events in Fig 12), depending on whether w_c(t) = 0 or w_c(t) ≠ 0, respectively. During this process, the value of w_c(t) is first incremented (2 time steps later) and then decremented (2 time steps later again) back to its original value. In other words, the testing procedure induces a back and forth fluctuation of w_c(t), without finally modifying it from its initial value (this fluctuation is unfortunately unavoidable). A counter module is denoted as counter_module().

Detection modules

Detection modules are used to retrieve—or detect—the current computational and counter states of the machine being simulated. This information is then employed to simulate the next transition of the machine. More precisely, each input symbol a ∈ Σ ∪ {ϵ}, computational state q ∈ Q and counter states c ¯ 1 , … , c ¯ k ∈ C of the machine are associated with a corresponding detection module. This module is activated if and only if the current input bit processed by the network is precisely a, the current synaptic weights w_s(t) corresponds to the encoding of the computational state q, and the current synaptic weights w c 1 ( t ) , … , w c k ( t ) are the encodings of counter values with corresponding counter states c ¯ 1 , … , c ¯ k. Afterwards, the detection module sends suitable activations to the state and counter modules so as to simulate the next transition δ ( q , a , c ¯ 1 , … , c ¯ k ) = ( q ′ , o 1 , … , o k ) of the machine. Formally, a detection module detects if the activation value of cell post_s of the state module is equal to a certain value v, together with the fact that k signals from cells = 0 or ≠ 0 of the k counter modules are correctly received. The module is composed of 4 Boolean cells connected in a feedforward manner, as illustrated in Fig 13. It is connected to the input transmission module, the state module and the counter modules described above.

The activity of this module, illustrated in Fig 14, can be described as follows. Suppose that at time step t, cell c₁ is spiking and cell post_s has an activation value of v (with 0 ≤ v ≤ 1). Then, at time t + 1, both c₂ and c₃ spike (since they receive signals of intensity 1). At next time t + 2, two signals of intensities 1 k + 2 are transmitted to c₄. Suppose that at this same time step, c₄ also receives k signals from the counter modules. Then, c₄ receives k + 2 signals of intensities 1 k + 2, and hence spikes at time t + 3 (case 1 of Fig 14). By contrast, if at time step t, c₁ is spiking and post_s has an activation value of v′ > v (resp. v′ < v), then at time t + 1 only c₂ (resp. c₃) spikes. Hence, at time t + 2, c₄ receives less than k + 2 signals of intensities 1 k + 2, and thus stays quiet (cases 3 and 4 of Fig 14). Consequently, the ‘detection cell’ c₄ (blue cell of Fig 13) spikes if and only if post_s has an exact activation value of v and c₄ receives exactly k signals from its afferent connections. A detection module involving weights 1 - v , 1 + v , 1 k + 2 is denoted as detection_module(v, k).

Assembling the modules

Any given k-counter machine C k = ( Q , Σ , C , O , δ , 0 , F ) (where Σ = {0, 1} and Q = {0, …, n − 1}) can be simulated by a recurrent neural network N subjected to the STDP rules given by Eqs (2) and (3). The network is obtained by a suitable assembling of the modules described above. The architecture of N is illustrated in Fig 5, and its detailed construction is given by Algorithm 1. In short, the network N is composed of 1 input encoding module (line 1), 1 input transmission module (line 2), 1 state module (line 3), k counter modules (lines 4–6) and at most |Q|⋅| Σ ∪ {ϵ}| ⋅ 2^k = 3n2^k detection modules (lines 7–11). The modules are connected together according to the patterns described in lines 12–47. This makes a total of O ( n 2 k ) cells and O ( n k 2 k ) synapses, which, since the number of counters k is fixed, corresponds to O ( n ) cells and O ( n ) synapses. A recurrent neural networks obtained via Algorithm 1 is referred to as an STDP-based RNN.

Algorithm 1 Procedure which takes a k-counter machine as input and builds an STDP-based RNN that simulates it.

Require: k-counter machine C k = ( Q , Σ , C , O , δ , 0 , F ), where Σ = {0, 1} and Q = {0, …, n − 1}

                     // note: computational states are represented as integers

                      // *** INSTANTIATION OF THE MODULES ***

1: IN1 ← input_encoding_module()                // input encoding module

2: IN2 ← input_transmission_module()             // input transmission module

3: ST ← state_module(n − 1)                // state module (where n = |Q|)

4: for all j = 1, …, k do

5:  C(j) ← counter_module()                   // k counter modules

6: end for

7: for all tuple ( i , a , c ¯ 1 , … , c ¯ k ) ∈ Q × Σ ∪ { ϵ } × C k do

8:  if δ ( i , a , c ¯ 1 , … , c ¯ k ) is defined then

9:   DET ( i , a , c ¯ 1 , … , c ¯ k ) ← d e t e c t i o n _ m o d u l e ( a m i n + i · η , k )    // detection modules

10:  end if

11: end for

                      // *** CONNECTION BETWEEN MODULES ***

12: connect c₁₉ of IN1 to u₀ of IN2: weight 1       // input encoding to input transmission

13: connect c₂₀ of IN1 to u₁ of IN2: weight 1

14: connect tic of IN1 to u_ϵ of IN2: weight 1

15: for all j = 1, …, k do                  // input transmission to counters

16:  connect u₀, u₁, u_ϵ of IN2 to test of C(j): weight 1

17: end for

18: connect d_2,0, d_2,1, d_2,ϵ of IN2 to pre_s of ST: weight 1       // input transmission to state

19: for all tuple ( i , a , c ¯ 1 , … , c ¯ k ) ∈ Q × Σ ∪ { ϵ } × C k do

20:  if δ ( i , a , c ¯ 1 , … , c ¯ k ) = ( i ′ , o 1 , … , o k ) then

21:   connect d_3,a of IN2 to c₁ of DET ( i , a , c ¯ 1 , … , c ¯ k ): weight 1 // input transmission to detection

22:   connect post of ST to c₂ of DET ( i , a , c ¯ 1 , … , c ¯ k ): weight 1       // state to detection

23:   connect post of ST to c₃ of DET ( i , a , c ¯ 1 , … , c ¯ k ): weight −1

24:   if a ⩵ ϵ then                      //detection to input encoding

25:    connect c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ) to c₁₅ of IN1: weight −1

26:   end if

27:   if i′ − i > 0 then                      // detection to state

28:    connect c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ) to c_{3((n−1)−(i′−i))+1} of ST: weight 1

29:   else if i′ − i < 0 then

30:    connect c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ) to c ¯ 3 ( ( n - 1 ) - ( i ′ - i ) ) + 1 of ST: weight 1

31:   end if

32:   for all j = 1, …, k do                     // detection to counters

33:    if o_j ⩵ push then

34:     connect c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ) to cell push of C(j): weight 1

35:    else if o_j ⩵ pop then

36:     connect c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ) to cell pop of C(j): weight 1

37:    end if

38:   end for

39:  end if

40:  for all j = 1, …, k do                      // counters to detection

41:   if c ¯ j = = ⊥ then

42:    connect ‘= 0’ of C(j) to c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ): weight 1 k + 2

43:   else if c ¯ j = = ⊤ then

44:    connect ‘≠ 0’ of C(j) to c₄ of DET ( i , a , c ¯ 1 , … , c ¯ k ): weight 1 k + 2

45:   end if

46:  end for

47: end for

Turing completeness

We now prove that any k-counter machine is correctly simulated by its corresponding STDP-based RNN given by Algorithm 1. Since 2-counter machines are Turing complete, then so is the class of STDP-based RNNs. Towards this purpose, the following definitions need to be introduced.

Let N be an STDP-based RNN. The input cells of N are the cells in₀, in₁, end, tic of the input encoding module (cf. Fig 6, four blue cells of the first layer). Thus, inputs of N are vectors in B 4 whose successive components represent the spiking configurations of cells in₀, in₁, end, and tic, respectively. In order to describe the input streams of N, we consider the following vectors of B 4:

According to these notations, the input stream 0011end∅∅tic corresponds to the following sequence of vectors provided at successive time steps

i.e., to the successive spikes of cells in₀, in₀, in₁, in₁, end, followed by two times steps during which all cells are quiet, followed by a last spike of the cell tic.

For any binary input w = a₀ ⋯ a_p ∈ Σ*, let u w ∈ ( B 4 ) * be the corresponding input stream of N defined by

where a_i = 0 if a_i = 0 and a_i = 1 if a₁ = 0, for i = 0, …, p. In other words, the input stream u_w consists of successive spike from cells in₀ and in₁ (inputs a₀ ⋯ a_p), followed by one spike from cell end (input end), followed by K p + 1 ′ time steps during which nothing happens (inputs ∅⋯∅), followed by successive spikes from cell tic, interspersed by constant intervals of K time steps during which nothing happens (input blocks tic_i∅ ⋯ ∅). The value of K p + 1 ′ is chosen such that, at time step p + 2 + K′, the p + 1 successive bits of u_w are correctly stored into cell c₁₄ of the input encoding module. The value of K is chosen such that, after each spike of the tic cell, the updating of the state and counter modules can be achieved within K time steps. Taking K p + 1 ′ ≥ 3 ( p + 1 ) + 4 and K ≥ 17 + 3(n − 1) (where n = |Q|) satisfies these requirements. Note that K p + 1 ′ depends on the input length, while K is constant (for a given counter machine). An input stream of this form is depicted by the 4 bottom lines of Fig 15 (in this case K p + 1 ′ = 23 and K = 29). Besides, for each i ≥ 0, let t_i be the time step at which tic_i occurs. For instance, in Fig 15, one has t₀ = 30, t₁ = 60, t₂ = 90, t₃ = 120, …. Let also

be the synaptic weights w s ( t ) , w c 1 ( t ) , … , w c k ( t ) of the state and counter modules at time step t_i − 1 (i.e., 1 time step before tic_i has occurred), with the assumption that

For example, in Fig 15, the values of w s ( t ) , w c 1 ( t ) , w c 2 ( t ) over time are represented by the upper red and orange curves (pay attention to the different left-hand and right-hand scales associated to these curves): one has (ws,0,wc1,0,wc2,0)=(0.1,0,0),(ws,1,wc1,1,wc2,1)=(0.3,0,0),(ws,2,wc1,2,wc2,2)=(0.3,0.5,0.5),(ws,3,wc1,3,wc2,3)=(0.3,0.75,0.75), etc. Furthermore, let a i ″ ∈ Σ ∪ { ϵ } ∪ { ∅ } be defined by

In other words, a i ″ is the input symbol (possibly ϵ) processed by N between t_i and t_i+1. For instance, in Fig 15, the successive input bits processed by the network are displayed by the spiking patterns of the cells u_ϵ, u₀, u₁: one has a 0 ″ = ϵ (only u_ϵ spikes between t₀ and t₁), a 1 ″ = 0 (both u_ϵ and then u₀ spike between t₁ and t₂, but only u₀ leads to the activation of a detection module, even if this is not represented), a 2 ″ = 0 (u₀ spikes after u_ϵ between t₂ and t₃), a 3 ″ = 1 (u₁ spikes after u_ϵ between t₃ and t₄), etc.

Now, for any input stream u_w, the computation of N over u_w is the sequence

where l 2 = min { t i : a i ″ = ∅ , i ≥ 0 }. In other words, the computation of N over u_w is the sequence of successive values of w s ( t ) , a i ″ , w c 1 ( t ) , … , w c k ( t ), which are supposed to encode the successive states, input symbols and counter values of the machine to be simulated, respectively.

According to these considerations, we say that C k is simulated in real time by N, or equivalently that N simulates C k in real time, if and only if, for any input w ∈ Σ* with corresponding input stream u w ∈ ( B 4 ) *, the computations of C k over w (Eq (4)) and of N over u_w (Eq (5))

satisfy the following conditions:

for all i = 0, …, l₁, which implicitly implies that l₂ ≥ l₁ (recall that r₀ ≔ 0 and r n ≔ ∑ i = 1 n 1 2 i, for all n > 0). In other words, C k is simulated by N iff, on every input, the computations of C k is perfectly reflected by that of N: the sequence of input symbols processed by C k and N coincide (Condition (7)), and the successive computational states and counter values of C k are properly encoded into the successive synaptic weights of w s ( t ) , w c 1 ( t ) , … , w c k ( t ) of N, respectively (Conditions (6) and (8)). According to these considerations, each state n i ∈ N and counter value c j , i ∈ N of C k is encoded by the synaptic value w s ( t i - 1 ) = a m i n + n i · η ∈ Q and w c j ( t i - 1 ) = r c j , i ∈ Q, for j = 1, …, k, respectively. The real time aspect of the simulation is ensured by the fact that the successive time steps (t_i)_i≥0 involved in the computation N ( w ) are separated by a constant number of time steps K > 0. This means that the transitions of C k are simulated by N in fixed amount of time.

We now show that, in this precise sense, any k-counter machine is correctly simulated its corresponding STDP-based recurrent neural network.

Theorem 1. Let C k be a k-counter machine and N be the STDP-based RNN given by Algorithm 1 applied on C k. Then, C k is simulated in real time by N.

Proof. Let w = a₀ ⋯ a_p ∈ Σ* be some input and u w ∈ ( B 4 ) * be its corresponding input stream. Consider the two computations of C k on w (Eq (4)) and of N on u_w (Eq (5)), respectively:

We prove by induction on i that C k ( w ) and N ( u w ) satisfy Conditions (6)–(8), for all i = 0, …, l₁.

By definition, the first elements of C k ( w ) and N ( u w ) are

Hence, Conditions (6) and (8) are satisfied for i = 0, i.e.,

We now prove Condition (7) for i = 0. Towards this purpose, the following observations are needed. By construction and according to the value of K_p+1, at time t₀ − 1, cell c₁₄ of the input encoding module IN1 holds the encoding of the whole input w = a₀ ⋯ a_p (the latter being considered as a stack). The top element of this stack is a₀. Besides, according to Relations (9) and Algorithm 1 (lines 22–23 and 40–46), only the detection modules DET ( n 0 , a , c ¯ 1 , 0 , … , c ¯ k , 0 ), where a ∈ Σ ∪ {ϵ}, are susceptible have their cell c₄ activated between t₀ and t₁ (indeed, only these modules are capable of “detecting” the current synaptic value a_min + n₀ ⋅ η and counters states c 1 , 0 , … , c k , 0 involved in Relations (9)).

Now, consider the symbol a 0 ′ ∈ Σ ∪ { ϵ }. Then either a 0 ′ ∈ Σ or a 0 ′ = ϵ. As a first case, suppose that a 0 ′ ∈ Σ. Since a 0 ′ ≠ ϵ and a 0 ′ is the first symbol processed by C k during its computation over input w = a₀ ⋯ a_p (cf. Eq (4)), one necessarily has a 0 ′ = a 0. Thus, δ ( n 0 , a 0 ′ , c ¯ 1 , 0 , … , c ¯ k , 0 ) = δ ( n 0 , a 0 , c ¯ 1 , 0 , … , c ¯ k , 0 ), and the determinism of C k ensures that δ ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ) is undefined. According to Algorithm 1 (lines 7–11), the module DET ( n 0 , a 0 , c ¯ 1 , 0 , … , c ¯ k , 0 ) is instanciated, whereas DET ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ) is not. Hence, the dynamics of N between t₀ and t₁ goes as follows. At time t₀, the cell tic of IN1 sends a signal to u_ϵ of IN2 (Algorithm 1, line 14) which propagates to the detection modules associated to symbol ϵ (Algorithm 1, line 21). Since the module DET ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ) does not exist, it can certainly not be activated, and thus, the cell c₁₅ of IN1 will not be inhibited in return (Algorithm 1, line 24–26). The spike of c₁₅ will then trigger the sub-circuit of IN1 that pops the top element of the stack currently encoded in c₁₄, namely, the symbol a₀. This triggers the activation of c₁₉ or c₂₀ of IN1 depending on whether a₀ = 0 or a₀ = 1. This activity then propagates to cells u a 0 and next d 3 , a 0 of IN2 (Algorithm 1, lines 12–13). It propagates further to the detection modules of the form DET(⋅, a₀, ⋅, …, ⋅), and in particular to DET ( n 0 , a 0 , c ¯ 1 , 0 , … , c ¯ k , 0 ) (Algorithm 1, line 21). According to Relations (9), the cell c₄ of DET ( n 0 , a 0 , c ¯ 1 , 0 , … , c ¯ k , 0 ), and of this module only, will be activated, since it is the only module of this form capable of detecting the current weight w_s(t) = a_min + η ⋅ n₀ as well as the current counter states c ¯ 1 , 0 , … , c ¯ k , 0 (Algorithm 1, lines 22–23 and 40–46). This amounts to saying that the symbol a 0 ″ processed by N between t₀ and t₁ is equal to a₀. Therefore, a 0 ″ = a 0 = a 0 ′. This shows that in this case, Condition (7) holds for i = 0.

As a second case, suppose that a 0 ′ = ϵ. It follows that δ ( n 0 , a 0 ′ , c ¯ 1 , 0 , … , c ¯ k , 0 ) = δ ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ), and by Algorithm 1 (lines 7–11), the module DET ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ) is instanciated. Consequently, the dynamics of N between t₀ and t₁ goes as follows. At time t₀, the cell tic of IN1 sends a signal to u_ϵ of IN2 (Algorithm 1, line 14) which propagates to the module DET ( n 0 , ϵ , c ¯ 1 , 0 , … , c ¯ k , 0 ) (Algorithm 1, line 21). By Relations (9), the cell c₄ of this detection module, and of only this one, will be activated (Algorithm 1, lines 22–23 and 40–46). This amounts to saying that a 0 ″ = ϵ = a 0 ′. Therefore, in this case also, Condition (7) holds for i = 0.

For the induction step, let m < l₁, and suppose that Conditions (6)–(8) are satisfied for all i ≤ m. Let also o_1,m+1, …, o_k,m+1 ∈ O be the counter operations such that

By definition of the sequence C k ( w ), a m ′ ∈ Σ ∪ { ϵ } and the counter operations satisfy

By the induction hypothesis (Condition (7)), a m ″ = a m ′. The definition of a m ″ ensures that the cell c₄ of one and only one detection module DET ( q , a m ″ , c ¯ 1 , … , c ¯ k ) is activated between time steps t_m and t_m+1, for some q ∈ Q and some c ¯ 1 , … , c ¯ k ∈ C. But by the induction hypotheses (Conditions (6) and (8)), at time step t_m − 1, one has

Hence, Relations (12) and (13) and Algorithm 1 (lines 22–23 and 40–46) ensure that the module DET ( n m , a m ″ , c ¯ 1 , m , … , c ¯ k , m ), and only this one, has its cell c₄ activated between time steps t_m and t_m+1. By Relation (10), the cell c₄ of this detection module is connected to cell

of the state module ST (Algorithm 1, lines 27–31). Hence, the activation of this detection module between t_m and t_m+1 induces subsequent spiking patterns of the state module which, by construction, increments (if n_m+1 − n_m > 0) or decrements (if n_m+1 − n_m < 0) the synaptic weight w_s(t) by |n_m+1 − n_m| ⋅ η, and hence, changes it from its current value a_min + n_m ⋅ η (cf. Eq (12)) to the new value a_min + n_m ⋅ η + (n_m+1 − n_m) ⋅ η = a_min + n_m+1 ⋅ η. Note that each spiking pattern takes 3 time steps, and hence, the updating of w_s(t) takes at most 3(n − 1) time steps, where n is the number of states of C k (the longest update being when |n_m+1 − n_m| = n − 1, which takes 3(n − 1) time steps). Therefore, at time t_m+1 − 1, one has

This shows that Condition (6) is satisfied for i = m + 1.

Similarly, by Relation (10), the cell c₄ of the module DET ( n m , a m ″ , c ¯ 1 , m , … , c ¯ k , m ) is connected to cells push or pop of the counter module C(j) depending on whether o_j,m+1 ⩵ push or o_j,m+1 ⩵ pop, respectively, for j = 1, …, k (Algorithm 1, lines 32–38). Hence, the activation of the detection module DET ( n m , a m ″ , c ¯ 1 , m , … , c ¯ k , m ) between t_m and t_m+1 induces subsequent activations of the counter modules which, by construction, change the synaptic weights w c j ( t ) from their current value r c j , m to r o j , m + 1 ( c j , m ), for j = 1, …, k. Note that the updating of each w c j ( t ) takes only 3 time steps. Consequently, at time t_m+1 − 1, one has

By Relation (11), these equations can be rewritten as

This shows that Condition (8) is satisfied for i = m + 1.

We now show that Condition (7) holds for i = m + 1. By the induction hypothesis, one has ( a i ′ ) i = 0 m = ( a i ″ ) i = 0 m. We must prove that a m + 1 ′ = a m + 1 ″. By definition, elements from ( a i ′ ) i = 0 m and ( a i ″ ) i = 0 m belong to Σ ∪ {ϵ}. Let ( a i j ′ ) j = 0 p 1 (with p₁ ≤ m) and ( a i j ″ ) j = 0 p 2 (with p₂ ≤ m) be the subsequences formed by the non-empty symbols of ( a i ′ ) i = 0 m and ( a i ″ ) i = 0 m, respectively. The induction hypothesis ensures that p₁ = p₂ = p′ and

Moreover, by definition again, ( a i ′ ) i = 0 m is the sequence of empty and non-empty symbols processed by C k during the m + 1 first steps of its computation over input w = a₀⋯a_p (cf. Eq (4)). Hence, the subsequence of its non-empty symbols ( a i j ′ ) j = 0 p ′ corresponds precisely to the p′ + 1 successive letters of w, i.e.,

The fact that ϵ symbols of ( a i ′ ) i = 0 m vanish within concatenation together with Relation (15) yield the following equalities

Also, Relations (14) and (15) directly imply

Besides, as already mentioned, at time t₀ − 1, cell c₁₄ of module IN1 holds the encoding of input w = a₀⋯a_p (considered as a stack). Between times t₀ and t_m+1 − 1, the elements of ( a i ″ ) i = 0 m are successively processed by N (cf. Eq (5)). During this time interval, the successive non-empty symbols of ( a i ″ ) i = 0 m, i.e., the elements of ( a i j ″ ) j = 0 p ′ = ( a i ) i = 0 p ′ (cf. Relation (17)), are successively popped from w = a₀⋯a_p and the remaining string stored in cell c₁₄. Consequently, at time t_m+1 − 1, cell c₁₄ holds the encoding of the remaining string a_p′+1⋯a_p, and thus, its top element is a_p′+1.

From this point onwards, the proof of Relation (7) for the case i = 0 can be adapted to the present situation. In short, consider a m + 1 ′ ∈ Σ ∪ { ϵ }. Then either a m + 1 ′ ∈ Σ or a m + 1 ′ = ϵ. Note that in case a m + 1 ′ ∈ Σ, Relation (16) ensures that a m + 1 ′ = a p ′ + 1. Taking this fact into account and replacing variables a 0 , a 0 ′ , a 0 ″ , n 0 , c ¯ 1 , 0 , … , c ¯ k , 0 of the previous argument by a m + 1 , a m + 1 ′ , a m + 1 ″ , n m + 1 , c ¯ 1 , m + 1 , … , c ¯ k , m + 1, respectively, leads to a m + 1 ″ = a m + 1 ′. Therefore, Condition (7) holds for i = m + 1.

Finally, we show that STDP-based RNNs are Turing complete. Let N be an STDP-based RNN. Let also a c c , r e j ∈ Q be two specific values for w_s(t). For any binary input w = a₀⋯a_p ∈ Σ*, we say that w is accepted (resp. rejected) by N if the sequence N ( u w ) is finite, and its last element ( w s , l 2 , a l 2 ″ , w c 1 , l 2 , … , w c k , l 2 ) satisfies a l 2 ″ = ϵ and w s , l 2 = a c c (resp. w s , l 2 = r e j). The language recognized by N, denoted by L ( N ), is the set of inputs accepted by N. A language L ⊆ Σ* is recognizable by some STDP-based RNN if there exists some STDP-based RNN N such that L ( N ) = L.

Corollary 1. Let L ⊆ Σ* be some language. The language L is recognizable by some Turing machine if and only if L is recognizable by some STDP-based RNN.

Proof. Suppose that L is recognizable by some STDP-based RNN N. The construction described in Algorithm 1 ensures that N can be simulated by some Turing machine M. Hence, L is recognizable by some Turing machine M. Conversely, suppose that L is recognizable by some Turing machine M. Then L is also recognizable by some 2-counter machine C 2 [57]. By Theorem 1, L is recognizable by some STDP-based RNN N.

Simulations

We now illustrate the correctness of our construction by means of computer simulations.

First, let us recall that the 2-counter machine of Fig 4 recognizes the recursively enumerable (but non context-free and non regular) language {0ⁿ1ⁿ0ⁿ: n > 0}, i.e., the sequences of bits beginning with a strictly positive number of 0’s followed by the same number of 1’s and followed again by the same number of 0’s. For instance, inputs w₁ = 001100 and w₂ = 0011101 are respectively accepted and rejected by the machine. Based on the previous considerations, we implemented an STDP-based RNN simulating this 2-counter machine. The network contains 390 cells connected together according to the construction given by Algorithm 1. We also set a_min = η = 0.1 in the STDP rule of Eq (2). Two computations of this network over an accepting and a rejecting input stream are illustrated in Figs 15 and 16. These simulations illustrate the correctness of the construction described in Algorithm 1.

More specifically, the computation of the network over the input stream

which corresponds to the encoding of w₁ = 001100, is displayed in Fig 15. In this case, taking K = 17 + 3(5 − 1) = 29 suffices for the correctness of the simulation (since the largest possible state update, in terms of the states’ indices, is a change from q₅ to q₁). The lower raster plot displays the spiking activities of some of the cells of the network belonging to the input encoding module (in₀, in₁, end, tic), the input transmission module (u₀, u₁, u_ϵ), the state module (pres_s, post_s) and the two counter modules (p u s h , p o p , t e s t , p r e c k , p o s t c k , = 0 , ≠ 0, for k = 1, 2).

From time step t = 0 to t = 6, the encoding of the input stream 001100 is transmitted to the network via activations of cells in₀, in₁ and end (blue pattern). Between t = 6 and t = 30, the input pattern is encoded into activation values of sigmoid cells in the input encoding module, as illustrated in Fig 7. From t = 30 onwards, the tic cell is activated every 30 time steps in order to trigger the successive computational steps of the network. Each spike of the tic cell induces a subsequent spike of u_ϵ one time step later. At this moment, the network tries to simulate an ϵ-transition of the counter machine. If such a transition is possible, the network performs it: this is the case at time steps t = 31, 181. Otherwise, the input encoding module retrieves the next input bit to be processed, and activates the corresponding cell u₀ or u₁ (blue pattern): this is the case at time steps t = 71, 101, 131, 161, 221, 251. In Fig 15 (cells u₀, u₁, u_ϵ), we can see that on this input stream, the network processes the sequence of input symbols ϵ0011ϵ00.

Every time the network receives an input symbol (ϵ, 0 or 1), it simulates one transition of the counter machine associated to this input. The successive computational states of the machine are encoded into the successive values taken by w_s(t) (cf. Fig 15, red curve in the upper graph). The changes in these synaptic weights are induced by the spiking patterns of cells pre_s and post_s (red patterns). The successive counter states of the machine, i.e., ‘zero’ or ‘non-zero’, are given by the activations of cells ‘= 0’ or ‘≠0’ of the counter modules, respectively (black patterns). The consecutive counter operations are given by the activations of cells push, pop and test (black patterns). The successive counter values of the machine are encoded into the successive values taken by w c 1 ( t ) and w c 2 ( t ) (orange curves of the upper graph). The changes in these synaptic weights are induced by the spiking pattern of cells p r e c j and p o s t c j, for j = 1, 2 (orange patterns). The pics along these curves are caused by the testing procedures which increment and decrement back the values of the synapses without finally modifying their current values (cf. description of the counter module).

The computation of the network over input stream u w 1 can be described by the successive synaptic weights ( w s ( t ) , w c 1 ( t ) , w c 2 ( t ) ) at time steps t = 30k, for 1 ≤ k ≤ 10. In this case, one has

Recall that state n and counter value x of C k are encoded by the synaptic weights w_s(t) = a_min + n ⋅ η and w_c(t) = r_x in N, respectively. Accordingly, the previous values correspond to the encodings of the following states and counter values (q, c₁, c₂) of the counter machine:

These are the correct computational states and counter values encountered by the machine along the computation of input w₁ = 001100 (cf. Fig 4). Therefore, the network simulates the counter machine correctly. The fact that the computations of the machine and the network terminate in state 4 and with w_s(t) = 0.5 = 0.1 + 4 ⋅ η, respectively, means that inputs w₁ and u w 1 are accepted by both systems.

As another example, the computation of the network over the input stream

which corresponds to the encoding of w₂ = 0011101, is displayed in Fig 16 (cells u₀, u₁, u_ϵ). We see that on this input stream, the network processes the sequence of input symbols ϵ0011ϵ101. The successive synaptic weights ( w s ( t ) , w c 1 ( t ) , w c 2 ( t ) ) at time steps t = 30k, for 1 ≤ k ≤ 10 are

These values correspond to the encodings of the following states and counter values (q, c₁, c₂) of the counter machine:

These are the correct computational states and counter values encountered by the machine working over input w₂ = 0011101 (cf. Fig 4). Therefore, the network simulates the counter machine correctly. The fact that the computations of the machine and the network terminate in state 1 and with w_s(t) = 0.2 = 0.1 + 1 ⋅ η, respectively, means that inputs w₁ and u w 1 are rejected by both systems.

Discussion

We proposed a novel Turing complete paradigm of neural computation where the essential information is encoded into discrete synaptic levels rather than into spiking configurations, activation values or (attractor) dynamics of neurons. More specifically, we showed that any 2-counter machine—and thus any Turing machine—can be simulated by a recurrent neural network subjected to two kinds of spike-timing-dependent plasticity (STDP) mechanisms. The finitely many computational states and infinitely many counter values of the machine are encoded into finitely and infinitely many synaptic levels, respectively. The transitions between states and counter values are achieved via the two STDP rules. In short, the network operates as follows. First, the input stream is encoded and stored into the activation value of a specific analog neuron. Then, every time a tic input signal is received, the network tries to simulate an ϵ-transition of the machine. If such a transition is possible, the network simulates it. Otherwise, the network retrieves from its memory the next input bit to be processed, and simulates a regular transition associated with this input. These results have been illustrated by means of computer simulations. An STDP-based recurrent neural network simulating a specific 2-counter machine has been implemented and its dynamics analyzed.

We emphasize once again that the possibility to simulate ϵ-transitions is (unfortunately) necessary to the achievement of Turing completeness. Indeed, it is well-known that the class of k-counter machines that do not make use of ϵ-transitions is not Turing complete, for any k > 0. For instance, the language L = {w#w: w ∈ {0, 1}*} (the strings of bits separated by a symbol # whose prefix and suffix are the same), is recursively enumerable, but cannot be recognized by a k-counter machine without ϵ-transitions. The input encoding module, as intricate as it is, ensures the implementation of this feature. It encodes and stores the incoming input stream so as to be able to subsequently intersperse the successive regular transitions (associated to regular input symbols) with ϵ-transitions (associated to ϵ symbols). By contrast, a k-counter machine without ϵ-transitions could be simulated by an STDP-based neural network working in an online fashion. The successive input symbols would be processed as they arrive, and a regular transition be simulated for each successive symbol. An STDP-based neural net (as described in Fig 5) without input encoding module could simulate a k-counter machine without ϵ-transitions. One would just need to add sufficiently many delay layers to its input transmission module in order to have enough time to emulate each regular transition.

In the present context, the STDP-based RNNs are capable of simulating Turing machines working in the accepting mode (i.e., machines that provide accepting or rejecting decisions of their inputs by halting in an accepting or a rejecting state, respectively). But it would be possible to adapt the construction to simulate Turing machines working also in the generative mode (i.e., machines that write the successive words of a language on their output tape, in an enumerative way). To this end, we would need to simulate the program and work tape of M by an STDP-based RNN N (as described in Theorem 1), and the output tape of M by an additional neural circuit N o u t plugged to N. Broadly speaking, the simulation process could be achieved as follows:

• Every non-output move of M is simulated by the STDP-based RNN N in the usual way (cf. Theorem 1).

• Every time M is generating a new word w = a₁⋯a_n on its output tape, use the circuit N o u t to build step by step the encoding r ¯ w = ∑ i = 1 n 2 a i + 1 4 i ∈ [ 0 , 1 ] of w and store this value in a designated neuron c (as described in the paragraph “Input encoding module”).

• When M has finished generating w, use the circuit N o u t to transfer the value r ¯ w of c to another neuron c′, to set the activation value of c back to 0, and to output the successive bits of w by popping the the stack r ¯ w stored in c′ (again, as described in the paragraph “Input encoding module”).

In this way, the STDP-based RNN N plugged to the circuit N o u t could work as a language generator: it outputs bit by bit the successive words of the language L generated by M. The implementation of the circuit N o u t is along the lines of what is described in the paragraph “input encoding module”.

Concerning the complexity issue, our model uses O ( n ) neurons and O ( n ) synapses to simulate a counter machine with n states. Moreover, the simulation works in real-time, since every computational step of the counter machine can be simulated in a fixed amount of 17 + 3(n − 1) time steps (17 time steps to transmit the next input bit up to the end of the detection modules, and at most 3(n − 1) time steps to perform the state and counter updates). In the context of rational-weighted sigmoidal neural networks, the seminal result from Siegelmann and Sontag uses 886 Boolean and analog neurons to simulate a universal Turing machine [4]. Recent results show that Turing completeness can be achieved with a minimum of 3 analog neurons only, the other ones being Boolean [58]. As for spiking neural P systems, Turing universality can be achieved with 3 or 4 neurons only, but this comes at the price of exponential time and space overheads (see [59], Table 1). In our case, the complexity of Turing universality is expected to be investigated in detail in a future work.

Regarding synaptic-based computation, a somehow related approach has already been pursued in the P system framework with the consideration of spiking neural P systems with rules on synapses [60]. In this case, synapses are considered as computational units triggering exchanges of spikes between neurons. The proposed model is shown to be Turing universal. It is claimed that “placing the spiking and forgetting rules on synapses proves to be a powerful feature, both simpler proofs and smaller universal systems are obtained in comparison with the case when the rules are placed in the neurons” [60]. In this context however, the information remains encoded into the number of spikes hold by the neurons, referred to as the “configuration” of the system. By contrast, in our framework, the essential information—the computational states and counter values—is encoded into discrete synaptic levels, and their updates achieved via synaptic plasticity rules.

As already mentioned, it has been argued that in biological neural networks “synapses change their strength by jumping between discrete mechanistic states rather than by simply moving up and down in a continuum of efficacy” [56]. These considerations represent “a new paradigm for understanding the mechanistic underpinnings of synaptic plasticity, and perhaps also the roles of such plasticity in higher brain functions” [56]. In addition, “much work remains to be done to define and understand the mechanisms and roles these states play” [56]. In our framework, the computational states and counter values of the machine are encoded into discrete synaptic states. However, the input stream to be processed is still encoded into the activation value of a specific analog neuron. It would be interesting to develop a paradigm where this feature also is encoded into synapses. Moreover, it would be interesting to extend the proposed paradigm of computation to the consideration of more biological STDP rules.

It is worth noting that synaptic-based and neuron-based computational paradigms are not opposite conceptions, but intertwined processes instead. Indeed, changes in synaptic states are achieved via the elicitation of specific neuronal spiking patterns (which modify the synaptic strengths via STDP). The main difference between these two conceptions is whether the essential information is encoded and memorized into synaptic states or into spiking configurations, activation values or (attractor) dynamics of neurons.

In biology, real brain circuits do certainly not operate by simulating abstract finite state machines. And with our work, we do intend to argue in this sense. Rather, our intention is to show that a bio-inspired Turing complete paradigm of abstract neural computation—centered on the concept of synaptic plasticity—is not only theoretically possible, but also potentially exploitable. The idea of representing and storing essential information into discrete synaptic levels is, we believe, novel and worthy of consideration. It represents a paradigm shift in the field of neural computation.

Finally, the impacts of the proposed approach are twofold. From a practical perspective, contemporary developments in neuromorphic computing provide the possibility to implement neurobiological architectures on very-large-scale integration (VLSI) systems, with the aim of mimicking neuronal circuits present in the nervous system [61, 62]. The implementation of our model on VLSI technologies would lead to the realization of new kinds of analog neuronal computers. The computational and learning capabilities of these neural systems could then be studied directly from the hardware point of view. And the integrated circuits implementing our networks might be suitable for specific applications. Besides, from a Machine Learning (ML) perspective, just as the dynamics of biological neural nets inspired neuronal-based learning algorithms, in this case also, the STDP-based recurrent neural networks might eventually lead to the development of new ML algorithms.

From a theoretical point of view, we hope that the study of neuro-inspired paradigms of abstract computation might contribute to the understanding of both biological and artificial intelligences. We believe that similarly to the foundational work from Turing, which played a crucial role in the practical realization of modern computers, further theoretical considerations about neural- and natural-based models of computation shall contribute to the emergence of novel computational technologies, and step by step, open the way to the next computational generation.

Supporting information

S1 Files [zip]
Python code.