# Refined Kolmogorov Complexity of Analog, Evolving and Stochastic Recurrent
Neural Networks

Jérémie Cabessa  Yann Strozecki  Laboratoire DAVID, UVSQ – University Paris-
Saclay, 78035 Versailles, France jeremie.cabessa<EMAIL_ADDRESS>Institute of Computer Science of the Czech Academy of Sciences,
18207 Prague 8, Czech Republic

###### Abstract

We provide a refined characterization of the super-Turing computational power
of analog, evolving, and stochastic neural networks based on the Kolmogorov
complexity of their real weights, evolving weights, and real probabilities,
respectively. First, we retrieve an infinite hierarchy of classes of analog
networks defined in terms of the Kolmogorov complexity of their underlying
real weights. This hierarchy is located between the complexity classes
$\mathbf{P}$ and $\mathbf{P/poly}$. Then, we generalize this result to the
case of evolving networks. A similar hierarchy of Kolomogorov-based complexity
classes of evolving networks is obtained. This hierarchy also lies between
$\mathbf{P}$ and $\mathbf{P/poly}$. Finally, we extend these results to the
case of stochastic networks employing real probabilities as source of
randomness. An infinite hierarchy of stochastic networks based on the
Kolmogorov complexity of their probabilities is therefore achieved. In this
case, the hierarchy bridges the gap between $\mathbf{BPP}$ and
$\mathbf{BPP/log^{*}}$. Beyond proving the existence and providing examples of
such hierarchies, we describe a generic way of constructing them based on
classes of functions of increasing complexity. For the sake of clarity, this
study is formulated within the framework of echo state networks. Overall, this
paper intends to fill the missing results and provide a unified view about the
refined capabilities of analog, evolving and stochastic neural networks.

###### keywords:

Recurrent Neural Networks; Echo state networks; Computational Power;
Computability Theory; Analog Computation; Stochastic Computation; Kolmogorov
Complexity.

##  1 Introduction

Philosophical considerations aside, it can reasonably be claimed that several
brain processes are of a computational nature. “The idea that brains are
computational in nature has spawned a range of explanatory hypotheses in
theoretical neurobiology” [20]. In this regard, the question of the
computational capabilities of neural networks naturally arises, among many
others.

Since the early 1940s, the theoretical approach to neural computation has been
focused on comparing the computational powers of neural network models and
abstract computing machines. In 1943, McCulloch and Pitts proposed a modeling
of the nervous system as a finite interconnection of logical devices and
studied the computational power of “nets of neurons” from a logical
perspective [62]. Along these lines, Kleene and Minsky proved that recurrent
neural networks composed of McCulloch and Pitts (i.e., Boolean) cells are
computationally equivalent to finite state automata [44, 64]. These results
paved the way for a future stream of research motivated by the expectation to
implement abstract machines on parallel hardware architectures (see for
instance [21, 1, 45, 38, 34, 69, 83]).

In 1948, Turing introduced the B-type unorganized machine, a kind of neural
network composed of interconnected NAND neuronal-like units [89]. He suggested
that the consideration of sufficiently large B-type unorganized machines could
simulate the behavior of a universal Turing machine with limited memory. The
Turing universality of neural networks involving infinitely many Boolean
neurons has been further investigated (see for instance in [71, 32, 25, 24,
80]). Besides, Turing brilliantly anticipated the concepts of “learning” and
“training” that would later become central to machine learning. These concepts
took shape with the introduction of the perceptron, a formal neuron that can
be trained to discriminate inputs using Hebbian-like learning [77, 78, 33].
But the computational limitations of the perceptron dampened the enthusiasms
for artificial neural networks [65]. The ensuing winter of neural networks
lasted until the 1980s, when the popularization of the backpropagation
algorithm, among other factors, paved the way for the great success of deep
learning [79, 81].

Besides, in the late 50’s, von Neumann proposed an alternative approach to
brain information processing from the hybrid perspective of digital and analog
computations [68]. Along these lines, Siegelmann and Sontag studied the
capabilities of sigmoidal neural networks, (instead of Boolean ones). They
showed that recurrent neural networks composed of linear-sigmoid cells and
rational synaptic weights are Turing complete [88, 37, 67]. This result has
been generalized to a broad class of sigmoidal networks [43].

Following the developments in analog computation [84], Siegelmann and Sontag
argued that the variables appearing in the underlying chemical and physical
phenomena could be modeled by continuous rather than discrete (rational)
numbers. Accordingly, they introduced the concept of an analog neural network
– a sigmoidal recurrent neural net equipped with real instead of rational
weights. They proved that analog neural networks are computationally
equivalent to Turing machines with advice, and hence, decide the complexity
class $\mathbf{P/poly}$ in polynomial time of computation [87, 86]. Analog
networks are thus capable of super-Turing capabilities and could capture
chaotic dynamical features that cannot be described by Turing machines [82].
Based to these considerations, Siegelmann and Sontag formulated the so-called
Thesis of Analog Computation – an analogous to the Church-Turing thesis in the
realm of analog computation – stating that no reasonable abstract analog
device can be more powerful than first-order analog recurrent neural networks
[87, 84].

Inspired by the learning process of neural networks, Cabessa and Siegelmann
studied the computational capabilities of evolving neural networks [10, 12].
In summary, evolving neural networks using either rational, real, or binary
evolving weights are all equivalent to analog neural networks. They also
decide the class $\mathbf{P/poly}$ in polynomial time of computation.

The computational power of stochastic neural networks has also been
investigated in detail. For rational-weighted networks, the addition of a
discrete source of stochasticity increases the computational power from
$\mathbf{P}$ to $\mathbf{BPP/log^{*}}$, while for the case of real-weighted
networks, the capabilities remain unchanged to the $\mathbf{P/poly}$ level
[85]. On the other hand, the presence of analog noise would strongly reduce
the computational power of the systems to that of finite state automata, or
even below [4, 57, 61].

Based on these considerations, a refined approach to the computational power
of recurrent neural networks has been undertaken. On the one hand, the sub-
Turing capabilities of Boolean rational-weighted networks containing $0$, $1$,
$2$ or $3$ additional sigmoidal cells have been investigated [90, 91]. On the
other hand, a refinement of the super-Turing computational power of analog
neural networks has been described in terms of the Kolmogorov complexity of
the underlying real weights [3]. The capabilities of analog networks with
weights of increasing Kolmogorov complexity shall stratify the gap between the
complexity classes $\mathbf{P}$ and $\mathbf{P/poly}$.

The capabilities of analog and evolving neural networks have been generalized
to the context of infinite computation, in connection with the attractor
dynamics of the networks [13, 11, 14, 16, 15, 6, 17, 7, 18]. In this
framework, the expressive power of the networks is characterized in terms of
topological classes from the Cantor space (the space of infinite bit streams).
A refinement of the computational power of the networks based on the
complexity of the underlying real and evolving weights has also been described
in this context [8, 9].

The computational capabilities of spiking neural networks (instead of
sigmoidal one) has also been extensively studied [54, 55]. In this approach,
the computational states are encoded into the temporal differences between
spikes rather than within the activation values of the cells. Maass proved
that single spiking neurons are strictly more powerful than single threshold
gates [59, 60]. He also characterized lower and upper bounds on the complexity
of networks composed of classical and noisy spiking neurons (see [47, 49, 51,
52, 58, 56] and [48, 50], respectively). He further showed that networks of
spiking neurons are capable of simulating analog recurrent neural networks
[53].

In the 2000s, Păun introduced the concept of a P system – a highly parallel
abstract model of computation inspired by the membrane-like structure of the
biological cell [72, 70]. His work led to the emergence of a highly active
field of research. The capabilities of various models of so-called neural P
systems have been studied (see for instance [75, 39, 76, 73, 74]). In
particular, neural P systems provided with a bio-inspired source of
acceleration were shown to be capable of hypercomputational capabilities,
spanning all levels of the arithmetical hierarchy [19, 26].

In terms of practical applications, recurrent neural networks are natural
candidates for sequential tasks, involving time series or textual data for
instance. Classical recurrent architectures, like LSTM and GRU, have been
applied with great success in many situations [29]. A $3$-level formal
hierarchy of the sub-Turing expressive capabilities of these architectures,
based on the notions of space complexity and rational recurrence, has been
established [63]. Echo state networks are another kind of recurrent neural
networks enjoying an increasing popularity due to their training efficiency
[41, 40, 42, 46]. The computational capabilities of echo state networks have
been studied from the alternative perspective of universal approximation
theorems [36, 35]. In this context, echo state networks are shown to be
universal, in the sense of being capable of approximating different classes of
filters of infinite discrete time signals [30, 31, 27, 28]. These works fit
within the field of functional analysis rather than computability theory.

In this paper, we extend the refined Kolmogorov-based complexity of analog
neural networks [3] to the cases of evolving and stochastic neural networks
[12, 85]. More specifically, we provide a refined characterization of the
super-Turing computational power of analog, evolving, and stochastic neural
networks based on the Kolmogorov complexity of their real weights, evolving
weights, and real probabilities, respectively. First, we retrieve an infinite
hierarchy of complexity classes of analog networks defined in terms of the
Kolmogorov complexity of their underlying real weights. This hierarchy is
located between the complexity classes $\mathbf{P}$ and $\mathbf{P/poly}$.
Using a natural identification between real numbers and infinite sequences of
bits, we generalize this result to the case of evolving networks. Accordingly,
a similar hierarchy of Kolomogorov-based complexity classes of evolving
networks is obtained. This hierarchy also lies between $\mathbf{P}$ and
$\mathbf{P/poly}$. Finally, we extend these results to the case of stochastic
networks employing real probabilities as source of randomness. An infinite
hierarchy of complexity classes of stochastic networks based on the Kolmogorov
complexity of their real probabilities is therefore achieved. In this case,
the hierarchy bridges the gap between $\mathbf{BPP}$ and
$\mathbf{BPP/log^{*}}$. Beyond proving the existence and providing examples of
such hierarchies, we describe a generic way of constructing them based on
classes of functions of increasing complexity. Technically speaking, the
separability between non-uniform complexity classes is achieved by means of a
generic diagonalization technique, a result of interest per se which improves
upon the previous approach [3]. For the sake of clarity, this study is
formulated within the framework of echo state networks. Overall, this paper
intends to fill the missing results and provide a unified view about the
refined capabilities of analog, evolving and stochastic neural networks.

This paper is organized as follows. Section 2 describes the related works.
Section 3 provides the mathematical notions necessary to this study. Section 4
presents recurrent neural networks within the formalism of echo state
networks. Section 5 introduces the different models of analog, evolving and
stochastic recurrent neural networks, and establishes their tight relations to
non-uniform complexity classes defined in terms of Turing machines with
advice. Section 6 provides the hierarchy theorems, which in turn, lead to the
descriptions of strict hierarchies of classes of analog, evolving and
stochastic neural network. Section 7 offers some discussion and concluding
remarks.

##  2 Related Works

Kleene and Misnky showed the equvalence between Boolean recurrent neural
networks and finite state automata [44, 64]. Siegelmann and Sontag proved the
Turing universality of rational-weighted neural networks [88]. Kilian and
Siegelmann generalized the result to a broader class of sigmoidal neural
networks [43]. In connection with analog computation, Siegelmann and Sontag
characterized the super-Turing capabilities of real-weighted neural networks
[88, 82, 86]. Cabessa and Siegelmann extended the result to evolving neural
networks [12]. The computational power of various kinds of stochastic and
noisy neural networks has been characterized [84, 4, 57, 61]. Sima graded the
sub-Turing capabilites of Boolean networks containing $0$, $1$, $2$ or $3$
additional sigmoidal cells [90, 91]. Balcázar et al. hierarchized the super-
Turing computational power of analog networks in terms of the Kolmogorov
complexity of their underlying real weights [3]. Cabessa et al. pursued the
study of the computational capabilities of analog and evolving neural networks
from the perspective of infinite computation [13, 11, 14, 16, 15, 6, 17, 7,
18].

Besides, the computational power of spiking neural networks has been
extensively studied by Maass [54, 55, 59, 60, 47, 49, 51, 52, 58, 56, 48, 50,
53]. In addition, since the 2000s, the field of P systems, which involves
neural P systems in particular, has been booming (see for instance [72, 70,
75, 39, 76, 73, 74]). The countless variations of proposed models are
generally Turing complete.

Regarding modern architectures, a hierarchy of the sub-Turing expressive power
of LSTM and GRU neural networks has been established [63]. Furthermore, the
universality of echo state networks has been studied from the perspective of
universal approximation theorems [30, 31, 27, 28].

##  3 Preliminaries

The binary alphabet is denoted by $\Sigma=\\{0,1\\}$, and the set of finite
words, finite words of length $n$, infinite words, and finite or infinite
words over $\Sigma$ are denoted by $\Sigma^{*}$, $\Sigma^{n}$,
$\Sigma^{\omega}$, and $\Sigma^{\leq\omega}$, respectively. Given some finite
or infinite word $w\in\Sigma^{\leq\omega}$, the $i$-th bit of $w$ is denoted
by $w_{i}$, the sub-word from index $i$ to index $j$ is $w[i:j]$, and the
length of $w$ is $|w|$, with $|w|=\infty$ if $w\in\Sigma^{\omega}$.

A Turing machine (TM) is defined in the usual way. A Turing machine with
advice (TM/A) is a TM provided with an additional advice tape and function
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$. On every input $w\in\Sigma^{n}$ of
length $n$, the machine first queries its advice function $\alpha(n)$, writes
this word on its advice tape, and then continues its computation according to
its finite program. The advice $\alpha$ is called prefix if $m\leq n$ implies
that $\alpha(m)$ is a prefix of $\alpha(n)$, for all $m,n\in\mathbb{N}$. The
advice $\alpha$ is called unbounded if the length of the successive advice
words tends to infinity, i.e., if
$\lim_{n\rightarrow\infty}|\alpha(n)|=\infty$.111Note that if $\alpha$ is not
unbounded, then it can be encoded into the program of a TM, and thus, doesn’t
add any computational power to the TM model. In this work, we assume that
every advice $\alpha$ is prefix and unbounded, which ensures that
$\lim_{n\rightarrow\infty}\alpha(n)\in\Sigma^{\omega}$ is well-defined. For
any non-decreasing function $f:\mathbb{N}\rightarrow\mathbb{N}$, the advice
$\alpha$ is said to be of size $f$ if $|\alpha(n)|=f(n)$, for all
$n\in\mathbb{N}$. We let $\mathrm{poly}$ be the set of univariate polynomials
with integer coefficients and $\mathrm{log}$ be the set of functions of the
form $n\rightarrow C\log(n)$ where $C\in\mathbb{N}$. The advice $\alpha$ is
called polynomial or logarithmic if it is of size $f\in\mathrm{poly}$ or
$f\in\mathrm{log}$, respectively. A TM/A $\mathcal{M}$ equipped with some
prefix unbounded advice is assumed to satisfy the following additional
consistency property: for any input $w\in\Sigma^{n}$, $\mathcal{M}$ accepts
$w$ using advice $\alpha(n)$ iff $\mathcal{M}$ accepts $w$ using advice
$\alpha(n^{\prime})$, for all $n^{\prime}\geq n$.

The class of languages decidable in polynomial time by some TM is
$\mathbf{P}$. The class of languages decidable in time
$t:\mathbb{N}\rightarrow\mathbb{N}$ by some TM/A with advice $\alpha$ is
denoted by $\mathbf{TMA}[\alpha,t]$. Given some class of advice functions
$\mathcal{A}\subseteq({\Sigma^{*}})^{\mathbb{N}}$ and some class of time
functions $\mathcal{T}\subseteq\mathbb{N}^{\mathbb{N}}$, we naturally define

$\mathbf{TMA}\left[\mathcal{A},\mathcal{T}\right]=\bigcup_{\alpha\in\mathcal{A}}\bigcup_{t\in\mathcal{T}}\mathbf{TMA}\left[\alpha,t\right].$

The class of languages decidable in polynomial time by some TM/A with
polynomial prefix and non-prefix advice are $\mathbf{P/poly^{*}}$ and
$\mathbf{P/poly}$, respectively. It can be noticed that
$\mathbf{P/poly^{*}}=\mathbf{P/poly}$.

A probabilistic Turing machine (PTM) is a TM with two transition functions. At
each computational step, the machine chooses one or the other transition
function with probability $\tfrac{1}{2}$, independently from all previous
choices, and updates its state, tapes’ contents, and heads accordingly. A PTM
$\mathcal{M}$ is assumed to be a decider, meaning that for any input $w$, all
possible computations of $\mathcal{M}$ end up either in an accepting or in a
rejecting state. Accordingly, the random variable corresponding to the
decision ($0$ or $1$) that $\mathcal{M}$ makes at the end of its computation
over $w$ is denoted by $\mathcal{M}(w)$. Given some language
$L\subseteq\Sigma^{*}$, we say that the PTM $\mathcal{M}$ decides $L$ in time
$t:\mathbb{N}\rightarrow\mathbb{N}$ if, for every $w\in\Sigma^{*}$,
$\mathcal{M}$ halts in $t(|w|)$ steps regardless of its random choices, and
$Pr[\mathcal{M}(w)=1]\geq\tfrac{2}{3}$ if $w\in L$ and
$Pr[\mathcal{M}(w)=0]\geq\tfrac{2}{3}$ if $w\not\in L$. The class of languages
decidable in polynomial time by some PTM is $\mathbf{BPP}$. A probabilistic
Turing machine with advice (PTM/A) is a PTM provided with an additional advice
tape and function $\alpha:\mathbb{N}\rightarrow\Sigma^{*}$. The class of
languages decided in time $t$ by some PTM/A with advice $\alpha$ is denoted by
$\mathbf{PTMA}[\alpha,t]$. Given some class of advice functions
$\mathcal{A}\subseteq({\Sigma^{*}})^{\mathbb{N}}$ and some class of time
functions, we also define

$\mathbf{PTMA}\left[\mathcal{A},\mathcal{T}\right]=\bigcup_{\alpha\in\mathcal{A}}\bigcup_{t\in\mathcal{T}}\mathbf{PTMA}\left[\alpha,t\right].$

The class of languages decidable in polynomial time by some PTM/A with
logarithmic prefix and non-prefix advice are $\mathbf{BPP/log^{*}}$ and
$\mathbf{BPP/log}$, respectively. In this probabilistic case however, it can
be shown that $\mathbf{BPP/log^{*}}\subsetneq\mathbf{BPP/log}$.

In the sequel, we will be interested in the size of the advice functions.
Hence, we define the following non-uniform complexity classes.222This
definition is non-standard. Usually, non-uniform complexity classes are
defined with respect to a class of advice functions
$\mathcal{H}\subseteq(\Sigma^{*})^{\mathbb{N}}$ instead of a class of advice
functions’ size $\mathcal{F}\subseteq\mathbb{N}^{\mathbb{N}}$. Given a class
of languages (or associated machines) $\mathcal{C}\subseteq 2^{\Sigma^{*}}$
and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we say that
$L\in\mathcal{C}/f^{*}$ if there exist some $L^{\prime}\in\mathcal{C}$ and
some prefix advice function $\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ such
that, for all $n\in\mathbb{N}$ and for all $w\in\Sigma^{n}$, the following
properties hold:

  1. (i)

$|\alpha(n)|=f(n)$, for all $n\geq 0$;

  2. (ii)

$w\in L\Leftrightarrow\langle w,\alpha(n)\rangle\in L^{\prime}$;

  3. (iii)

$\langle w,\alpha(n)\rangle\in L^{\prime}\Leftrightarrow\langle
w,\alpha(k)\rangle\in L^{\prime},\text{ for all }k\geq n$.

Given a class of functions $\mathcal{F}\subseteq\mathbb{N}^{\mathbb{N}}$, we
naturally set

$\mathcal{C}/\mathcal{F}^{*}=\bigcup_{f\in\mathcal{F}}\mathcal{C}/f^{*}.$

The non-starred complexity classes $\mathcal{C}/f$ and
$\mathcal{C}/\mathcal{F}$ are defined analogously, except that the prefix
property of $\alpha$ and the last condition are not required. For instance,
the class of languages decidable in polynomial time by some Turing machine
(resp. probabilistic Turing machines) with prefix advice of size $f$ is
$\mathbf{P}/f^{*}$ (resp. $\mathbf{BPP}/f^{*}$).

Besides, for any $w=w_{0}w_{1}w_{2}\cdots\in\Sigma^{\leq\omega}$, we consider
the base-2 and base-4 encoding functions
$\delta_{2}:\Sigma^{\leq\omega}\rightarrow[0,1]$ and
$\delta_{4}:\Sigma^{\leq\omega}\rightarrow[0,1]$ respectively defined by

$\delta_{2}(w)=\sum_{i=0}^{|w|}\frac{w_{i}+1}{2^{i+1}}\text{ ~{}and~{}
}\delta_{4}(w)=\sum_{i=0}^{|w|}\frac{2w_{i}+1}{4^{i+1}}.$

The use of base $4$ ensures that $\delta_{4}$ is an injection. Setting
$\Delta:=\delta_{4}(\Sigma^{\omega})\subseteq[0,1]$ ensures that the
restriction $\delta_{4}:\Sigma^{\leq\omega}\rightarrow\Delta$ is bijective,
and thus that $\delta^{-1}$ is well-defined on the domain $\Delta$. In the
sequel, for any real $r\in\Delta$, its base-4 expansion will be generally be
denoted as
$\bar{r}=r_{0}r_{1}r_{2}\cdots\in\delta_{4}^{-1}(r)\in\Sigma^{\omega}$. For
any $R\subseteq\Delta$, we thus define $\bar{R}=\\{\bar{r}:r\in R\\}$.

Finally, for every probability space $\Omega$ and every events
$A_{1},\dots,A_{n}\subseteq\Omega$, the probability that at least one event
$A_{i}$ occurs can be bounded by the union bound defined by

$\mathrm{Pr}\left(\bigcup_{i=1}^{n}A_{i}\right)\leq\sum_{i=1}^{n}\mathrm{Pr}\left(A_{i}\right).$

##  4 Recurrent Neural Networks

We consider a specific model of recurrent neural networks complying with the
echo state networks architecture [41, 40, 42, 46]. More specifically, a
recurrent neural network is composed of an input layer, a pool of
interconnected neurons sometimes referred to as the reservoir, and an output
layer, as illustrated in Figure 1. The networks read and accept or reject
finite words over the alphabet $\Sigma=\\{0,1\\}$ using a input-output
encoding described below. Accordingly, they are capable of performing
decisions of formal languages.

######  Definition 1.

A rational-weighted recurrent neural network (RNN) is a tuple

$\mathcal{N}=\left(\mathbf{x},\mathbf{h},\mathbf{y},\mathbf{W_{in}},\mathbf{W_{res}},\mathbf{W_{out}},\mathbf{h}^{0}\right)$

where

  * •

$\mathbf{x}=(x_{0},x_{1})$ is a sequence of two input cells, the data input
$x_{0}$ and the validation input $x_{1}$;

  * •

$\mathbf{h}=(h_{0},\dots,h_{K-1})$ is a sequence of $K$ hidden cells,
sometimes referred to as the reservoir;

  * •

$\mathbf{y}=(y_{0},y_{1})$ is a sequence of two output cells, the data output
$y_{0}$ and the validation output $y_{1}$;

  * •

$\mathbf{W_{in}}\in\mathbb{Q}^{K\times(2+1)}$ is a matrix of input weights and
biases, where $w_{ij}$ is the weight from input $x_{j}$ to cell $h_{i}$, for
$j\neq 2$, and $w_{i2}$ is the bias of $h_{i}$;

  * •

$\mathbf{W_{res}}\in\mathbb{Q}^{K\times K}$ is a matrix of internal weights,
where $w_{ij}$ is the weight from cell $h_{j}$ to cell $h_{i}$;

  * •

$\mathbf{W_{out}}\in\mathbb{Q}^{2\times K}$ is a matrix of output weights,
where $w_{ij}$ is the weight from cell $h_{j}$ to output $y_{i}$;

  * •

$\mathbf{h}^{0}=(h^{0}_{0},\dots,h^{0}_{K-1})\in[0,1]^{K}$ is the initial
state of $\mathcal{N}$, where each component $h_{i}^{0}$ is the initial
activation value of cell $h_{i}$.

The activation value of the cell $x_{i}$, $h_{j}$ and $y_{k}$ at time $t$ is
denoted by $x_{i}^{t}\in\\{0,1\\}$, $h_{j}^{t}\in[0,1]$ and
$y_{k}^{t}\in\\{0,1\\}$, respectively. Note that the activation values of
input and output cells are Boolean, as opposed to those of the hidden cells.
The input, output and (hidden) state of $\mathcal{N}$ at time $t$ are the
vectors

$\mathbf{x}^{t}=(x_{0}^{t},x_{1}^{t})\in\mathbb{B}^{2},~{}~{}~{}\mathbf{y}^{t}=(y_{0}^{t},y_{1}^{t})\in\mathbb{B}^{2}~{}\text{
and }~{}\mathbf{h}^{t}=(h_{0}^{t},\dots,h_{K-1}^{t})\in[0,1]^{K}\,,$

respectively. Given some input $\mathbf{x}^{t}$ and state $\mathbf{h}^{t}$ at
time $t$, the state $\mathbf{h}^{t+1}$ and the output $\mathbf{y}^{t+1}$ at
time $t+1$ are computed by the following equations:

$\displaystyle\mathbf{h}^{t+1}$ $\displaystyle=$
$\displaystyle\sigma\left(\mathbf{W_{in}}(\mathbf{x}^{t}:1)+\mathbf{W_{res}}\mathbf{h}^{t}\right)$
(1) $\displaystyle\mathbf{y}^{t+1}$ $\displaystyle=$
$\displaystyle\theta\left(\mathbf{W_{out}}\mathbf{h}^{t+1}\right)$ (2)

where $(\mathbf{x}^{t}:1)$ denotes the vector $(x_{0}^{t},x_{1}^{t},1)$, and
$\sigma$ and $\theta$ are the linear sigmoid and the hard-threshold functions
respectively given by

$\sigma(x)=\begin{cases}0&\text{if }x<0\\\ x&\text{if }0\leq x\leq 1\\\
1&\text{if }x>1\end{cases}\text{ ~{}~{}and~{}~{}
}\theta(x)=\begin{cases}0&\text{if }x<0\\\ 1&\text{if }x\geq 1\end{cases}.$

The constant value $1$ in the input vector $(\mathbf{x}^{t},1)$ ensure that
the hidden cells $\mathbf{h}$ receive the last column of
$\mathbf{W_{in}}\in\mathbb{Q}^{K\times(2+1)}$ as biases at each time step
$t\geq 0$. In the sequel, the bias of cell $h_{i}$ will be denoted as
$w_{i2}$.

Figure 1: A recurrent neural network. The network is composed of two Boolean
input cells (data and validation), two Boolean output cells (data and
validation) and a set of $K$ hidden cells, the reservoir, that are recurrently
interconnected. The weight matrices $\mathbf{W_{in}}$, $\mathbf{W_{res}}$, and
$\mathbf{W_{out}}$ labeling the connections between these layers are
represented. In this illustration, the network reads the finite word $10100$
by means of its data and validation input cells (blue), and eventually rejects
it, as shown by the pattern of the data and validation output cells (red).

An input $\mathbf{x}$ of length $n$ for the network $\mathcal{N}$ is an
infinite sequence of inputs at successive time steps $t=0,1,2,\dots$, such
that the $n$ first validation bits are equal to $1$, while the remaining data
and validation bits are equal to $0$, i.e.,

$\mathbf{x}=\mathbf{x}^{0}\mathbf{x}^{1}\cdots\mathbf{x}^{n-1}\mathbf{0}^{\omega}\in\left(\mathbb{B}^{2}\right)^{\omega}$

where $\mathbf{x}^{i}=(x_{0}^{i},1)$ and $x_{0}^{i}\in\\{0,1\\}$, for
$i=1,\dots,n-1$, and $\mathbf{0}=(0,0)$. Suppose that the network
$\mathcal{N}$ is in the initial state $\mathbf{h}^{0}$ and that input
$\mathbf{x}$ is presented to $\mathcal{N}$ step by step. The dynamics given by
Equations (1) and (2) ensures that that $\mathcal{N}$ will generate the
sequences of states and outputs

$\displaystyle\mathbf{h}$ $\displaystyle=$
$\displaystyle\mathbf{h}^{0}\mathbf{h}^{1}\mathbf{h}^{2}\cdots\in\left([0,1]^{K}\right)^{\omega}$
$\displaystyle\mathbf{y}$ $\displaystyle=$
$\displaystyle\mathbf{y}^{1}\mathbf{y}^{2}\mathbf{y}^{3}\cdots\in\left(\mathbb{B}^{2}\right)^{\omega}$

step by step, where $\mathbf{y}:=\mathcal{N}(\mathbf{x})$ is the output of
$\mathcal{N}$ associated with input $\mathbf{x}$.

Now, let $w=w_{0}w_{1}\cdots w_{n-1}\in\Sigma^{*}$ be some finite word of
length $n$, let $\tau\in\mathbb{N}$ be some integer, and let
$f:\mathbb{N}\rightarrow\mathbb{N}$ be some non-decreasing function. The word
$w\in\Sigma^{*}$ can naturally be associated with the input

$\mathbf{w}=\mathbf{w}^{0}\mathbf{w}^{1}\cdots\mathbf{w}^{n-1}\mathbf{0}^{\omega}\in\left(\mathbb{B}^{2}\right)^{\omega}$

defined by $\mathbf{w}^{i}=(x^{i}_{0},x^{i}_{1})=(w_{i},1)$, for
$i=1,\dots,n-1$. The input pattern is thus given by

$\begin{array}[]{c c c c c c c c c c c c
c}x^{0}_{0}&x^{1}_{0}&x^{2}_{0}&\cdots&=&w_{0}&w_{1}&\cdots&w_{n-1}&0&0&0&\cdots\\\
x^{0}_{1}&x^{1}_{1}&x^{2}_{1}&\cdots&=&1&1&\cdots&1&0&0&0&\cdots\end{array}$

where the validation bits indicate whether an input is actively being
processed or not, and the corresponding data bits represent the successive
values of the input (see Figure 1). The word $w$ is said to be accepted or
rejected by $\mathcal{N}$ in time $\tau$ if the output

$\mathcal{N}(\mathbf{w})=\mathbf{y}=\mathbf{y}^{1}\mathbf{y}^{2}\cdots\mathbf{y}^{\tau}\mathbf{0}^{\omega}\in\left(\mathbb{B}^{2}\right)^{\omega}$

is such that $\mathbf{y^{i}}=(0,0)$, for $i=1,\dots,\tau-1$, and
$\mathbf{y}^{\tau}=(1,1)$ or $\mathbf{y}^{\tau}=(0,1)$, respectively. The
output pattern is thus given by

$\begin{array}[]{c c c c c c c c c c c
c}y^{0}_{0}&y^{1}_{0}&y^{2}_{0}&\cdots&=&0&0&\cdots&y^{\tau}_{1}&0&0&\cdots\\\
y^{0}_{1}&y^{1}_{1}&y^{2}_{1}&\cdots&=&0&0&\cdots&1&0&0&\cdots\end{array}$

where $y^{\tau}_{1}=1$ or $y^{\tau}_{1}=0$, respectively.

In addition, the word $w$ is said to be accepted or rejected by $\mathcal{N}$
in time $f$ if it is accepted or rejected in time $\tau\leq f(n)$,
respectively.333The choice of the letter $f$ (instead of $t$) for referring to
a computation time is deliberate, since the computation time of the networks
will later be linked to the advice length of the Turing machines. A language
$L\subseteq\Sigma^{*}$ is decided by $\mathcal{N}$ in time $f$ if for every
word $w\in\Sigma^{*}$,

$\displaystyle w\in L$ $\displaystyle\text{ implies that }\mathbf{w}\text{ is
accepted by $\mathcal{N}$ in time $f$ and}$ $\displaystyle w\not\in L$
$\displaystyle\text{ implies that }\mathbf{w}\text{ is rejected by
$\mathcal{N}$ in time $f$}.$

A language $L\subseteq\Sigma^{*}$ is decided by $\mathcal{N}$ in polynomial
time if there exists a polynomial $f$ such that $L$ is decided by
$\mathcal{N}$ in time $f$. If it exists, the language decided by $\mathcal{N}$
in time $f$ is denoted by $L_{f}(\mathcal{N})$. Besides, a network
$\mathcal{N}$ is said to be a decider if any finite word is eventually
accepted or rejected by it. In this case, the language decided by
$\mathcal{N}$ is unique and is denoted by $L(\mathcal{N})$. We will assume
that all the networks that we consider are deciders. s

Recurrent neural networks with rational weights have been shown to be
computationally equivalent to Turing machines [88].

######  Theorem 1.

Let $L\subseteq\Sigma^{*}$ be some language. The following conditions are
equivalent:

  1. (i)

$L$ is decidable by some TM;

  2. (ii)

$L$ is decidable by some RNN.

###### Proof.

(sketch) (ii) $\rightarrow$ (i): The dynamics of any RNN $\mathcal{N}$ is
governed by Equations (1) and (2), which involves only rational weights, and
thus can clearly be simulated by some Turing machine $\mathcal{M}$.

(i) $\rightarrow$ (ii): We provide a sketch of the original proof of this
result [88]. This proof is based on the fact that any finite (and infinite)
binary word can be encoded into and the activation value of a neuron, and
decoded from this activation value bit by bit. This idea will be reused in
some forthcoming proofs. First of all, recall that any TM $\mathcal{M}$ is
computationally equivalently to, and can be simulated in real time by, some
$p$-stack machine $\mathcal{S}$ with $p\geq 2$. We thus show that any
$p$-stack machine $\mathcal{S}$ can be simulated by some RNN $\mathcal{N}$.
Towards this purpose, we encode every stack content

$w=w_{0}\cdots w_{n-1}\in\\{0,1\\}^{*}$

as the rational number

$q_{w}=\delta_{4}(w)=\sum_{i=0}^{n-1}\frac{2\cdot w(i)+1}{4^{i+1}}\in[0,1].$

For instance, $w=1110$ is encoded into
$q_{w}=\frac{3}{4}+\frac{3}{16}+\frac{3}{64}+\frac{1}{256}$. With this base-4
encoding, the required stack operations can be performed by simple functions
involving the sigmoid-linear function $\sigma$, as described below:

  * •

Reading the top of the stack: $\mathrm{top}(q_{w})=\sigma(4q_{w}-2)$

  * •

Pushing $0$ into the stack:
$\mathrm{push_{0}}(q_{w})=\sigma(\frac{1}{4}q_{w}+\frac{1}{4})$

  * •

Pushing $1$ into the stack:
$\mathrm{push_{1}}(q_{w})=\sigma(\frac{1}{4}q_{w}+\frac{3}{4})$

  * •

Popping the stack:
$\mathrm{pop}(q_{w})=\sigma(4q_{w}-(2\mathrm{top}(q_{w})+1))$

  * •

Emptiness of the stack: $\mathrm{empty}(q_{w})=\sigma(4q_{w})$

Hence, the content $w$ of each stack can be encoded into the rational
activation value $q_{w}$ of a stack neuron, and the stack operations (reading
the top, pushing $0$ or $1$, popping and testing the emptiness) can be
performed by simple neural circuits implementing the functions described
above.

Based on these considerations, we can design an RNN $\mathcal{N}$ which
correctly simulates the $p$-stack machine $\mathcal{S}$. The network
$\mathcal{N}$ contains $3$ neurons per stack: one for storing the encoded
content of the stack, one for reading the top element of the stack, and one
for storing the answer of the emptiness test of the stack. Moreover,
$\mathcal{N}$ contains two pools of neurons implementing the computational
states and transition function of $\mathcal{S}$, respectively. For any
computational state, input bit, and contents of the stacks, $\mathcal{N}$
computes the next computational state and updates the stacks’ contents in
accordance with the transition function of $\mathcal{S}$. In this way, the
network $\mathcal{N}$ simulates the behavior of the $p$-stack machine
$\mathcal{S}$ correctly. The network $\mathcal{N}$ is illustrated in Figure 2.
∎

Figure 2: Construction of an RNN that simulates a $p$-stack machine.

It can be noticed that the simulation process described in the proof of
Theorem 1 is performed in real time. More precisely, if a language
$L\subseteq\Sigma^{*}$ is decided by some TM in time $f(n)$, then $L$ is
decided by some RNN in time $f(n)+O(n)$. Hence, when restricted to polynomial
time of computation, RNNs decide the complexity class $\mathbf{P}$.

######  Corollary 2.

Let $L\subseteq\Sigma^{*}$ be some language. The following conditions are
equivalent:

  1. (i)

$L\in\mathbf{P}$;

  2. (ii)

$L$ is decidable by some RNN in polynomial time.

##  5 Analog, Evolving and Stochastic Recurrent Neural Networks

We now introduce analog, evolving and stochastic recurrent neural networks,
which are all variants of the RNN model. In polynomial time, these models
capture the complexity classes $\mathbf{P/poly}$, $\mathbf{P/poly}$ and
$\mathbf{BPP/log^{*}}$, respectively, which all strictly contain the class
$\mathbf{P}$ and include non-recursive languages. According to these
considerations, these augmented models have been qualified as super-Turing.
For each model, a tight characterization in terms of Turing machines with
specific kinds of advice is provided.

###  5.1 Analog networks

An analog recurrent neural network (ANN) is an RNN as defined in Definition 1,
except that the weight matrices are real instead of rational [87]. Formally,
an ANN is an RNN

$\mathcal{N}=\left(\mathbf{x},\mathbf{h},\mathbf{y},\mathbf{W_{in}},\mathbf{W_{res}},\mathbf{W_{out}},\mathbf{h}^{0}\right)$

such that

$\mathbf{W_{in}}\in\mathbb{R}^{K\times(2+1)}\text{,~{}~{}}\mathbf{W_{res}}\in\mathbb{R}^{K\times
K}\text{~{}~{}and~{}~{}}\mathbf{W_{out}}\in\mathbb{R}^{2\times K}.$

The definitions of acceptance and rejection of words as well as of decision of
languages is the same as for RNNs.

It can been shown that any ANN $\mathcal{N}$ containing the irrational weights
$r_{1},\dots,r_{k}\in\mathbb{R}\setminus\mathbb{Q}$ is computationally
equivalent to some ANN $\mathcal{N}^{\prime}$ using only a single irrational
weight $r\in\mathbb{R}\setminus\mathbb{Q}$ such that
$r\in\Delta\subseteq[0,1]$ and $r$ is the bias $w_{02}$ of the hidden cell
$h_{0}$ [87]. Hence, without loss of generality, we restrict our attention to
such networks. Let $r\in\Delta$ and $R\subseteq\Delta$.

  * •

$\text{ANN}[r]$ denotes the class of ANNs such that all weights but $w_{02}$
are rational and $w_{02}=r$.

  * •

$\text{ANN}[R]$ denotes the class of ANNs such that all weights but $w_{02}$
are rational and $w_{02}\in R$.

In this definition, $r$ is allowed to be a rational number. In this case, an
$\text{ANN}[r]$ is just a specific RNN.

In exponential time of computation, analog recurrent neural networks can
decide any possible language. In fact, any language $L\subseteq\Sigma^{*}$ can
be encoded into the infinite word $\bar{r}_{L}\in\Sigma^{\omega}$, where the
$i$-th bit of $\bar{r}_{L}$ equals $1$ iff the $i$-th word of $\Sigma^{*}$
belongs to $L$, according to some enumeration of $\Sigma^{*}$. Hence, we can
build some ANN containing the real weight $r_{L}=\delta_{4}(\bar{r}_{L})$,
which, for every input $w$, decides whether $w\in L$ or $w\not\in L$ by
decoding $\bar{r}_{L}$ and reading the suitable bit. In polynomial time of
computation, however, the ANNs decide the complexity class $\mathbf{P/poly}$,
and hence, are computationally equivalent to Turing machines with polynomial
advice (TM/poly(A)). The following result holds [87]:

######  Theorem 3.

Let $L\subseteq\Sigma^{*}$ be some language. The following conditions are
equivalent:

  1. (i)

$L\in\mathbf{P/poly}$;

  2. (ii)

$L$ is decidable by some ANN in polynomial time.

Given some ANN $\mathcal{N}$ and some $q\in\mathbb{N}$, the truncated network
$\mathcal{N}|_{q}$ is defined as the network $\mathcal{N}$ whose all weights
and activation values are truncated after $q$ precision bits at each step of
the computation. The following result shows that, up to time $q$, the network
$\mathbb{N}$ can limit itself to $O(q)$ precision bits without affecting the
result of its computation [87].

######  Lemma 4.

Let $\mathcal{N}$ be some ANN computing in time
$f:\mathbb{N}\rightarrow\mathbb{N}$. Then, there exists some constant $c>0$
such that, for every $n\in\mathbb{N}$ and every input $w\in\Sigma^{n}$, the
networks $\mathcal{N}$ and $\mathcal{N}|_{cf(n)}$ produce the same outputs up
to time $f(n)$.

The computational relationship between analog neural networks and Turing
machines with advice can actually be strengthened. Towards this purpose, for
any non-decreasing function $f:\mathbb{N}\rightarrow\mathbb{N}$ and any class
of such functions $\mathcal{F}$, we define the following classes of languages
decided by analog neural networks in time $f$ and $\mathcal{F}$, respectively:

$\displaystyle\mathbf{ANN}\left[r,f\right]$ $\displaystyle=$
$\displaystyle\left\\{L\subseteq\Sigma^{\omega}:L=L_{f}(\mathcal{N})\text{ for
some }\mathcal{N}\in\text{ANN}[r]\right\\}$
$\displaystyle\mathbf{ANN}\left[R,\mathcal{F}\right]$ $\displaystyle=$
$\displaystyle\bigcup_{r\in
R}\bigcup_{f\in\mathcal{F}}\mathbf{ANN}\left[r,f\right].$

In addition, for any real $r\in\Delta$ and any function
$f:\mathbb{N}\rightarrow\mathbb{N}$, the prefix advice
$\alpha(\bar{r},f):\mathbb{N}\rightarrow\Sigma^{*}$ of length $f$ associated
with $r$ is defined by

$\alpha(\bar{r},f)(n)=r_{0}r_{1}\cdots r_{f(n)-1}$

for all $n\in\mathbb{N}$. For any set of reals $R\subseteq\Delta$ and any
class of functions $\mathcal{F}\subseteq\mathbb{N}^{\mathbb{N}}$, we naturally
set

$\alpha(\bar{R},\mathcal{F})=\bigcup_{\bar{r}\in\bar{R}}\bigcup_{f\in\mathcal{F}}\left\\{\alpha(\bar{r},f)\right\\}$

Conversely, note that any prefix unbounded advice
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ is of the form $\alpha(\bar{r},f)$,
where $\bar{r}=\lim_{n\rightarrow\infty}\alpha(n)\in\Sigma^{\omega}$ and
$f:\mathbb{N}\rightarrow\mathbb{N}$ is defined by $f(n)=|\alpha(n)|$.

The following result clarifies the tight relationship between analog neural
networks using real weights and Turing machines using related advices. Note
that the real weights of the networks correspond precisely to the advice of
the machines, and the computation time of the networks are related to the
advice length of the machines.

######  Proposition 5.

Let $r\in\Delta$ be some real weight and $f:\mathbb{N}\rightarrow\mathbb{N}$
be some non-decreasing function.

  1. (i)

$\mathbf{ANN}\left[r,f\right]\subseteq\mathbf{TMA}\left[\alpha(\bar{r},cf),O(f^{3})\right]$,
for some $c>0$.

  2. (ii)

$\mathbf{TMA}\left[\alpha(\bar{r},f),f\right]\subseteq\mathbf{ANN}\left[r,O(f)\right]$.

###### Proof.

(i) Let $L\in\mathbf{ANN}\left[r,f\right]$. Then, there exists some
$\text{ANN}[r]$ $\mathcal{N}$ such that $L_{f}(\mathcal{N})=L$. By Lemma 4,
there exists some constant $c>0$ such that the network $\mathcal{N}$ and the
truncated network $\mathcal{N}|_{cf(n)}$ produce the same outputs up to time
step $f(n)$, for all $n\in\mathbb{N}$. Now, consider Procedure 1 below. In
this procedure, all instructions except the query one (line 2) are recursive.
Besides, the simulation of each step of $\mathcal{N}|_{cf(n)}$ involves a
constant number of multiplications and additions of rational numbers, all
representable by $cf(n)$ bits, and can thus be performed in time $O(f^{2}(n))$
(for the products). Consequently, the simulation of the $f(n)$ steps of
$\mathcal{N}|_{cf(n)}$ can be performed in time $O(f^{3}(n))$. Hence,
Procedure 1 can be simulated by some TM/A $\mathcal{M}$ using advice
$\alpha(\bar{r},cf)$ in time $O(f^{3}(n))$. In addition, Lemma 4 ensures that
$w$ is accepted by $\mathcal{M}$ iff $w$ is accepted by $\mathcal{N}$, for all
$w\in\Sigma^{*}$. Hence, $L(\mathcal{M})=L(\mathcal{N})=L$, and therefore
$L\in\mathbf{TMA}\left[\alpha(\bar{r},cf),O(f^{3})\right]$.

Input: input $w\in\Sigma^{n}$

1 Query the advice $\alpha(\bar{r},cf)(n)=r_{0}r_{1}\cdots r_{cf(n)-1}$

2 for  _$t=0,1,\dots,f(n)-1$_ do

3 Simulate the truncated network $\mathcal{N}|_{cf(n)}$ which uses the
rational approximation $\tilde{r}=\delta_{4}(r_{0}r_{1}\cdots r_{cf(n)-1})$ of
$r$ as its weight;

return Output of $\mathcal{N}|_{cf(n)}$ over $w$ at time step $f(n)$

Procedure 1

(ii) Let $L\in\mathbf{TMA}\left[\alpha(\bar{r},f),f\right]$. Then, there
exists some TM/A $\mathcal{M}$ with advice $\alpha(\bar{r},f)$ such that
$L_{f}(\mathcal{M})=L$. We show that $\mathcal{M}$ can be simulated by some
analog neural network $\mathcal{N}$ with real weight $r$. The network
$\mathcal{N}$ simulates the advice tape of $\mathcal{M}$ as described in the
Proof of Theorem 1: the left and right contents of the tape are encoded and
stored into two stack neurons $x_{l}$ and $x_{r}$, respectively, and the tape
operations are simulated using appropriate neural circuits. On every input
$w\in\Sigma^{n}$, the network $\mathcal{N}$ works as follows. First,
$\mathcal{N}$ copies its real bias $r=\delta_{4}(r_{0}r_{1}r_{2}\cdots)$ into
some neuron $x_{a}$. Every time $\mathcal{M}$ reads some new advice bit
$r_{i}$, then $\mathcal{N}$ first pops $r_{i}$ from its neuron $x_{a}$, which
thus takes the updated activation value $\delta_{4}(r_{i+1}r_{i+2}\cdots)$,
and next pushes $r_{i}$ into neuron $x_{r}$. This process is performed in
constant time. At this point, neurons $x_{l}$ and $x_{r}$ contain the encoding
of the bits $r_{0}r_{1}\cdots r_{i}$. Hence, $\mathcal{N}$ can simulates the
recursive instructions of $\mathcal{M}$ in the usual way, in real time, until
the next bit $r_{i+1}$ is read [88]. Overall, $\mathcal{N}$ simulates the
behavior of $\mathcal{M}$ in time $O(f(n))$.

We now show that $\mathcal{M}$ and $\mathcal{N}$ output the same decision for
input $w$. If $\mathcal{M}$ does not reach the end of its advice word
$\alpha(n)$, the behaviors of $\mathcal{M}$ and $\mathcal{N}$ are identical,
and so are their outputs. If at some point, $\mathcal{M}$ reaches the end of
$\alpha(n)$ and reads successive blank symbols, then $\mathcal{N}$ continues
to pop the successive bits $r_{|\alpha(n)|}r_{|\alpha(n)|+1}\cdots$ from
neuron $x_{a}$, to push them into neuron $x_{r}$, and to simulates the
behavior of $\mathcal{M}$. In this case, $\mathcal{N}$ simulates the behavior
of $\mathcal{M}$ working with some extension of the advice $\alpha(n)$, which
by the consistency property of $\mathcal{M}$ (cf. Section 3), produces the
same output as if working with advice $\alpha(n)$. In this way, $w$ is
accepted by $\mathcal{M}$ iff $w$ is accepted by $\mathcal{N}$, and thus
$L(\mathcal{M})=L(\mathcal{N})$. Therefore,
$L\in\mathbf{ANN}\left[r,O(f)\right]$. ∎

The following corollary shows that the class of languages decided in
polynomial time by analog networks with real weights and by Turing machines
with related advices are the same.

######  Corollary 6.

Let $r\in\Delta$ be some real weight and $R\subseteq\Delta$ be some set of
real weights.

  1. (i)

$\mathbf{ANN}\left[r,\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha(\bar{r},\mathrm{poly}),\mathrm{poly}\right]$.

  2. (ii)

$\mathbf{ANN}\left[R,\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha(\bar{R},\mathrm{poly}),\mathrm{poly}\right]$.

###### Proof.

(i) Let $L\in\mathbf{ANN}\left[r,\mathrm{poly}\right]$. Then, there exists
$f\in\mathrm{poly}$ such that $L\in\mathbf{ANN}\left[r,f\right]$. By
Proposition 5–(i), $L\in\mathbf{TMA}\left[\alpha(\bar{r},cf),O(f^{3})\right]$,
for some $c>0$. Thus
$L\in\mathbf{TMA}\left[\alpha(\bar{r},\mathrm{poly}),\mathrm{poly}\right]$.
Conversely, let
$L\in\mathbf{TMA}\left[\alpha(\bar{r},\mathrm{poly}),\mathrm{poly}\right]$.
Then, there exist $f,f^{\prime}\in\mathrm{poly}$ such that
$L\in\mathbf{TMA}\left[\alpha(\bar{r},f^{\prime}),f\right]$. By the
consistency property of the TM/A, we can assume without loss of generality
that $f^{\prime}=f$. By Proposition 5–(ii),
$L\in\mathbf{ANN}\left[r,O(f)\right]$, and hence
$L\in\mathbf{ANN}\left[r,\mathrm{poly}\right]$.

(ii) This point follows directly from point (i) by taking the union over all
$r\in R$. ∎

###  5.2 Evolving networks

An evolving recurrent neural network (ENN) is an RNN where the weight matrices
can evolve over time inside a bounded space instead of staying static [12].
Formally, an ENN is a tuple

$\mathcal{N}=\left(\mathbf{x},\mathbf{h},\mathbf{y},\left(\mathbf{W^{\mathnormal{t}}_{in}}\right)_{t\in\mathbb{N}},\left(\mathbf{W^{\mathnormal{t}}_{res}}\right)_{t\in\mathbb{N}},\left(\mathbf{W^{\mathnormal{t}}_{out}}\right)_{t\in\mathbb{N}},\mathbf{h}^{0}\right)$

where $\mathbf{x},\mathbf{h},\mathbf{y},\mathbf{h}^{0}$ are defined as in
Definition 1, and

$\mathbf{W^{\mathnormal{t}}_{in}}\in\mathbb{Q}^{K\times(2+1)}\text{,~{}~{}}\mathbf{W^{\mathnormal{t}}_{res}}\in\mathbb{Q}^{K\times
K}\text{~{}~{}and~{}~{}}\mathbf{W^{\mathnormal{t}}_{out}}\in\mathbb{Q}^{2\times
K}.$

are input, reservoir and output weight matrices at time $t$ such that
$\|\mathbf{W^{\mathnormal{t}}_{in}}\|_{\max}=\|\mathbf{W^{\mathnormal{t}}_{res}}\|_{\max}=\|\mathbf{W^{\mathnormal{t}}_{out}}\|_{\max}\leq
C$ for some constant $C>1$ and for all $t\in\mathbb{N}$. The boundedness
condition expresses the fact that the synaptic weights are confined into a
certain range of values imposed by the biological constitution of the neurons.
The successive values of an evolving weight $w_{ij}$ is denoted by
$(w^{t}_{ij})_{t\in\mathbb{N}}$. The dynamics of an ENN is given by the
following adapted equations

$\displaystyle\mathbf{h}^{t+1}$ $\displaystyle=$
$\displaystyle\sigma\left(\mathbf{W^{\mathnormal{t}}_{in}}(\mathbf{x}^{t}:1)+\mathbf{W^{\mathrm{t}}_{res}}\mathbf{h}^{t}\right)$
(3) $\displaystyle\mathbf{y}^{t+1}$ $\displaystyle=$
$\displaystyle\theta\left(\mathbf{W^{\mathnormal{t}}_{out}}\mathbf{h}^{t+1}\right).$
(4)

The definition of acceptance and rejection of words and decision of languages
is the same as for RNNs.

In this case also, it can been shown that any ENN $\mathcal{N}$ containing the
evolving weights $\bar{e}_{1},\dots,\bar{e}_{n}\in[-C,C]^{\omega}$ is
computationally equivalent to some ENN $\mathcal{N}^{\prime}$ containing only
one evolving weight $\bar{e}\in[-C,C]^{\omega}$, such that $\bar{e}$ evolves
only among the binary values $0$ and $1$, i.e. $\bar{e}\in\Sigma^{\omega}$,
and $\bar{e}$ is the evolving bias $(w^{t}_{02})_{t\in\mathbb{N}}$ of the
hidden cell $h_{0}$ [12]. Hence, without loss of generality, we restrict our
attention to such networks. Let $\bar{e}\in\Sigma^{\omega}$ be some binary
evolving weight and $\bar{E}\subseteq\Sigma^{\omega}$.

  * •

$\text{ENN}[\bar{e}]$ denoted the class of ENNs such that all weights but
$w_{02}$ are static, and $(w^{t}_{02})_{t\in\mathbb{N}}=\bar{e}$.

  * •

$\text{ENN}[\bar{E}]$ denotes the class of ENNs such that all weights but
$w_{02}$ are static, and $(w^{t}_{02})_{t\in\mathbb{N}}\in\bar{E}$.

Like analog networks, evolving recurrent neural networks can decide any
possible language in exponential time of computation. In polynomial time, they
decide the complexity class $\mathbf{P/poly}$, and thus, are computationally
equivalent to Turing machines with polynomial advice (TM/poly(A)). The
following result holds [12]:

######  Theorem 7.

Let $L\subseteq\Sigma^{*}$ be some language. The following conditions are
equivalent:

  1. (i)

$L\in\mathbf{P/poly}$;

  2. (ii)

$L$ is decidable by some ENN in polynomial time.

An analogous version of Lemma 4 holds for the case of evolving networks [12].
Note that the boundedness condition on the weights is involved in this result.

######  Lemma 8.

Let $\mathcal{N}$ be some ENN computing in time
$f:\mathbb{N}\rightarrow\mathbb{N}$. Then, there exists some constant $c$ such
that, for every $n\in\mathbb{N}$ and every input $w\in\Sigma^{n}$, the
networks $\mathcal{N}$ and $\mathcal{N}|_{cf(n)}$ produce the same outputs up
to time $f(n)$.

Once again, the computational relationship between evolving neural networks
and Turing machines with advice can be strengthen. For this purpose, we define
the following classes of languages decided by evolving neural networks in time
$f$ and $\mathcal{F}$, respectively:

$\displaystyle\mathbf{ENN}\left[\bar{e},f\right]$ $\displaystyle=$
$\displaystyle\left\\{L\subseteq\Sigma^{\omega}:L=L_{f}(\mathcal{N})\text{ for
some }\mathcal{N}\in\text{ENN}[\bar{e}]\right\\}$
$\displaystyle\mathbf{ENN}\left[\bar{E},\mathcal{F}\right]$ $\displaystyle=$
$\displaystyle\bigcup_{\bar{e}\in\bar{E}}\bigcup_{f\in\mathcal{F}}\mathbf{ENN}\left[\bar{e},f\right].$

For any $\bar{e}\in\Sigma^{\omega}$ and any function
$f:\mathbb{N}\rightarrow\mathbb{N}$, we consider the prefix advice
$\alpha(\bar{e},f):\mathbb{N}\rightarrow\Sigma^{*}$ associated with $e$ and
$f$ defined by

$\alpha(\bar{e},f)(n)=e_{0}e_{1}\cdots e_{f(n)-1}$

for all $n\in\mathbb{N}$. Conversely, any prefix advice
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ is clearly of the form
$\alpha(\bar{e},f)$, where
$\bar{e}=\lim_{n\rightarrow\infty}\alpha(n)\in\Sigma^{\omega}$ and
$f(n)=|\alpha(n)|$ for all $n\in\mathbb{N}$.

The following relationships between neural networks with evolving weights and
Turing machines with related advice hold:

######  Proposition 9.

Let $e\in\Sigma^{\omega}$ be some binary evolving weight and
$f:\mathbb{N}\rightarrow\mathbb{N}$ be some non-decreasing function.

  1. (i)

$\mathbf{ENN}\left[\bar{e},f\right]\subseteq\mathbf{TMA}\left[\alpha(\bar{e},cf),O(f^{3})\right]$,
for some $c>0$.

  2. (ii)

$\mathbf{TMA}\left[\alpha(\bar{e},f),f\right]\subseteq\mathbf{ENN}\left[\bar{e},O(f)\right]$.

###### Proof.

The proof is very similar to that of Proposition 5.

(i) Let $L\in\mathbf{ENN}\left[\bar{e},f\right]$. Then, there exists some
$\text{ENN}[\bar{e}]$ $\mathcal{N}$ such that $L_{f}(\mathcal{N})=L$. By Lemma
8, there exists some constant $c>0$ such that the network $\mathcal{N}$ and
the truncated network $\mathcal{N}|_{cf(n)}$ produce the same outputs up to
time step $f(n)$, for all $n\in\mathbb{N}$. Now, consider Procedure 2 below.
In this procedure, all instructions except the query one are recursive.
Procedure 2 can be simulated by some TM/A $\mathcal{M}$ using advice
$\alpha(\bar{e},f)$ in time $O(f^{3}(n))$, as described in the proof of
Proposition 5. In addition, $\mathcal{M}$ and $\mathcal{N}$ decide the same
language $L$, and therefore
$L\in\mathbf{TMA}\left[\alpha(\bar{e},f),O(f^{3})\right]$.

Input: input $w\in\Sigma^{n}$

1 Query the advice $\alpha(\bar{e},f)(n)=e_{0}e_{1}\cdots e_{cf(n)-1}$

2 for  _$t=0,1,\dots,f(n)$_ do

3 Simulate the truncated network $\mathcal{N}|_{cf(n)}$ which uses
$w^{t}_{02}=e_{t}$ as the current value if its evolving weight;

return Output of $\mathcal{N}|_{cf(n)}$ over $w$ at time step $f(n)$

Procedure 2

(ii) Let $L\in\mathbf{TMA}\left[\alpha(\bar{e},f),f\right]$. Then, there
exists to some TM/A $\mathcal{M}$ with advice $\alpha(\bar{e},f)$ such that
$L_{f}(\mathcal{M})=L$. The machine $\mathcal{M}$ can be simulated by the
network $\mathcal{N}$ with evolving weight $\bar{e}=e_{0}e_{1}e_{2}\cdots$ as
follows. First, $\mathcal{N}$ simultaneously counts and pushes into a stack
neuron $x_{a}$ the successive bits of $\bar{e}$ as they arrive. Then, for
$k=1,2,\dots$ and until it produces a decision, $\mathcal{N}$ proceeds as
follows. If necessary, $\mathcal{N}$ waits for $x_{a}$ to contain more than
$2^{k}$ bits, copies the content $e_{0}e_{1}\cdots e_{2^{k}}\cdots$ of $x_{a}$
in reverse order into another stack neuron $x_{a^{\prime}}$, and simulates
$\mathcal{M}$ with advice $e_{0}e_{1}\cdots e_{2^{k}}\cdots$ in real time.
Every time $\mathcal{M}$ reads a new advice bit, $\mathcal{N}$ tries to access
it from its stack $x_{a^{\prime}}$. If $x_{a^{\prime}}$ does not contain this
bit, then $\mathcal{N}$ restart the whole process with $k+1$. When
$k=\log(f(n))$, the stack $x_{a}$ contains $2^{k}=f(n)$ bits, which ensures
that $\mathcal{N}$ properly simulates $\mathcal{M}$ with advice
$e_{0}e_{1}\cdots e_{f(n)-1}$. Hence, the whole simulation process is achieved
in time $O(\sum_{k=1}^{\log(f(n))}2^{k})=O(2^{\log(f(n))+1})=O(f(n))$. In this
way, $\mathcal{M}$ and $\mathcal{N}$ decide the same language $L$, and
$\mathcal{M}$ is simulated by $\mathcal{N}$ in time $O(f)$. Therefore,
$L\in\mathbf{ENN}\left[\bar{e},O(f)\right]$. ∎

The class of languages decided in polynomial time by evolving networks and
Turing machines using related evolving weights and advices are the same.

######  Corollary 10.

Let $\bar{e}\in\Sigma^{\omega}$ be some binary evolving weight and
$\bar{E}\subseteq\Sigma^{\omega}$ be some set of binary evolving weights.

  1. (i)

$\mathbf{ENN}\left[\bar{e},\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha(\bar{e},\mathrm{poly}),\mathrm{poly}\right]$.

  2. (ii)

$\mathbf{ENN}\left[\bar{E},\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha(\bar{E},\mathrm{poly}),\mathrm{poly}\right]$.

###### Proof.

The proof is similar to that of Corollary 6. ∎

###  5.3 Stochastic networks

A stochastic recurrent neural network (SNN) is an RNN as defined in Definition
1, except that the network contains additional stochastic cells as inputs
[84]. Formally, an SNN is an RNN

$\mathcal{N}=\left(\mathbf{x},\mathbf{h},\mathbf{y},\mathbf{W_{in}},\mathbf{W_{res}},\mathbf{W_{out}},\mathbf{h}^{0}\right)$

such that $\mathbf{x}=(x_{0},x_{1},x_{2},\cdots,x_{k+1})$, where $x_{0}$ and
$x_{1}$ are the data and validation input cells, respectively, and
$x_{2},\dots,x_{k+1}$ are $k$ additional stochastic cells. The dimension of
the input weight matrix is adapted accordingly, namely
$\mathbf{W_{in}}\in\mathbb{R}^{K\times((k+2)+1)}$. Each stochastic cell
$x_{i}$ is associated with a probability $p_{i}\in[0,1]$, and at each time
step $t\geq 0$, the activation of the cell $x^{t}_{i}$ takes value $1$ with
probability $p_{i}$, and value $0$ with probability $1-p_{i}$. The dynamics of
an SNN is then governed by Equations (1) and (2), but with the adapted inputs
$\mathbf{x}^{t}=(x^{t}_{0},x^{t}_{1},x^{t}_{2},\cdots,x^{t}_{k+1})\in\mathbb{B}^{k+2}$
for all $t\geq 0$.

For some SNN $\mathcal{N}$, we assume that any input $w=w_{0}w_{1}\cdots
w_{n-1}\in\Sigma^{*}$ is decided by $\mathcal{N}$ in the same amount of time
$\tau(n)$, regardless of the random pattern of the stochastic cells
$x^{t}_{i}\in\\{0,1\\}$, for all $i=2,\dots,k+1$. Hence, the number of
possible computations of $\mathcal{N}$ over $w$ is finite. The input $w$ is
accepted (resp. rejected) by $\mathcal{N}$ if the number of accepting (resp.
rejecting) computations over the total number of computations on $w$ is
greater than or equal to $2/3$. This means that the error probability of
$\mathcal{N}$ is bounded by $1/3$. If $f:\mathbb{N}\rightarrow\mathbb{N}$ is a
non-decreasing function, we say that $w$ is accepted or rejected by
$\mathcal{N}$ in time $f$ if it is accepted or rejected in time $\tau(n)\leq
f(n)$, respectively. We assume that any SNN is a decider. The definition of
decision of languages is the same as in the case of RNNs.

Once again, any SNN is computationally equivalent to some SNN with only one
stochastic cell $x_{2}$ associated with a real probability $p\in\Delta$ [84].
Without loss of generality, we restrict our attention to such networks. Let
$p\in\Delta$ be some probability and $P\subseteq\Delta$.

  * •

$\text{SNN}[p]$ denotes the class of SNNs such that the probability of the
stochastic cell $x_{2}$ is equal to $p$.

  * •

$\text{SNN}[P]$ denotes the class of SNNs such that the probability of the
stochastic cell $x_{2}$ is equal to some $p\in P$.

In polynomial time of computation, the SNNs with rational probabilities decide
the complexity class $\mathbf{BPP}$. By contrast, the SNNs with real
probabilities decide the complexity class $\mathbf{BPP/log^{*}}$, and hence,
are computationally equivalent to probabilistic Turing machines with
logarithmic advice (PTM/log(A)). The following result holds [84]:

######  Theorem 11.

Let $L\subseteq\Sigma^{*}$ be some language. The following conditions are
equivalent:

  1. (i)

$L\in\mathbf{BPP/log^{*}}$;

  2. (ii)

$L$ is decidable by some SNN in polynomial time.

As for the two previous models, the computational relationship between
stochastic neural networks and Turing machines with advice can be precised. We
define the following classes of languages decided by stochastic neural
networks in time $f$ and $\mathcal{F}$, respectively:

$\displaystyle\mathbf{SNN}\left[p,f\right]$ $\displaystyle=$
$\displaystyle\left\\{L\subseteq\Sigma^{\omega}:L=L_{f}(\mathcal{N})\text{ for
some }\mathcal{N}\in\text{SNN}[p]\right\\}$
$\displaystyle\mathbf{SNN}\left[P,\mathcal{F}\right]$ $\displaystyle=$
$\displaystyle\bigcup_{p\in
P}\bigcup_{f\in\mathcal{F}}\mathbf{SNN}\left[p,f\right].$

The tight relationships between stochastic neural networks using real
probabilities and Turing machines using related advices can now be described.
In this case however, the advice of the machines are logarithmically related
to the computation time of the networks.

######  Proposition 12.

Let $p\in\Delta$ be some real probability and
$f:\mathbb{N}\rightarrow\mathbb{N}$ be some non-decreasing function.

  1. (i)

$\mathbf{SNN}[p,f]\subseteq\mathbf{PTMA}\left[\alpha(\bar{p},\log(5f)),O(f^{3})\right]$.

  2. (ii)

$\mathbf{PTMA}\left[\alpha(\bar{p},\log(f)),f\right]\subseteq\mathbf{SNN}\left[p,O(f^{2})\right]$.

###### Proof.

(i) Let $L\in\mathbf{SNN}\left[p,f\right]$. Then, there exists some
$\text{SNN}[p]$ $\mathcal{N}$ deciding $L$ in time $f$. Note that the
stochastic network $\mathcal{N}$ can be considered as a classical rational-
weighted RNN with an additional input cell $x_{2}$. Since $\mathcal{N}$ has
rational weights, it can be noticed that up to time $f(n)$, the activation
values of its neurons are always representable by rationals of $O(f(n))$ bits.
Now, consider Procedure 3 below. This procedure can then be simulated by some
PTM/A $\mathcal{M}$ using advice $\alpha(\bar{p},\log(5f))$ in time
$O(f^{3})$, as described in the proof of Proposition 5.

It remains to show that $\mathcal{N}$ and $\mathcal{M}$ decide the same
language $L$. For this purpose, consider a hypothetical device
$\mathcal{M}^{\prime}$ working as follows: at each time $t$,
$\mathcal{M}^{\prime}$ takes the sequence of bits $\bar{b}$ generated by
Procedure 3 and concatenates it with some infinite sequence of bits
$\bar{b}^{\prime}\in\Sigma^{\omega}$ drawn independently with probability
$\tfrac{1}{2}$, thus producing the infinite sequence
$\bar{b}\bar{b}^{\prime}\in\Sigma^{\omega}$. Then, $\mathcal{M}^{\prime}$
generates a bit $c^{\prime}_{t}$ iff $\bar{b}\bar{b}^{\prime}<_{lex}\bar{p}$,
which happens precisely with probability $p$, since $p=\delta_{2}(\bar{p})$
[2]. Finally, $\mathcal{M}^{\prime}$ simulates the behavior of $\mathcal{N}$
at time $t$ using the stochastic bit $x_{2}^{t}=c^{\prime}_{t}$. Clearly,
$\mathcal{M}^{\prime}$ and $\mathcal{N}$ produce random bits with same
probability $p$, behave in the same way, and thus decide the same language
$L$. We now evaluate the error probability of $\mathcal{M}$ at deciding $L$,
by comparing the behaviors of $\mathcal{M}$ and $\mathcal{M}^{\prime}$. Let
$w\in\Sigma^{n}$ be some input and let

$\bar{p}_{\mathcal{M}}=\alpha(\bar{p},\log(5f))(n)=p_{0}p_{1}\cdots
p_{\log(5f(n))-1}\text{ ~{}and~{}
}p_{\mathcal{M}}=\delta_{2}(\bar{p}_{\mathcal{M}}).$

According to Procedure 3, at each time step $t$, the machine $\mathcal{M}$
generates $c_{t}=1$ iff $\bar{b}<_{lex}\bar{p}_{\mathcal{M}}$, which happens
precisely with probability $p_{\mathcal{M}}$, since
$p_{\mathcal{M}}=\delta_{2}(\bar{p}_{\mathcal{M}})$ [2]. On the other hand,
$\mathcal{M}^{\prime}$ generates $c^{\prime}_{t}=1$, with probability $p$,
showing that $\mathcal{M}$ and $\mathcal{M}^{\prime}$ might differ in their
decisions. Since $\bar{p}_{\mathcal{M}}$ is a prefix of $\bar{p}$, it follows
that $p_{\mathcal{M}}\leq p$ and

$p-p_{\mathcal{M}}=\sum_{i=\log(5f(n))}^{\infty}\frac{p_{i}}{2^{i+1}}\leq\frac{1}{2^{\log(5f(n))}}=\frac{1}{5f(n)}.$

In addition, the bits $c_{t}$ and $c^{\prime}_{t}$ are generated by
$\mathcal{M}$ and $\mathcal{M}^{\prime}$ based on the sequences $\bar{b}$ and
$\bar{b}\bar{b}^{\prime}$ satisfying $\bar{b}<_{lex}\bar{b}\bar{b}^{\prime}$.
Hence,

$\mathrm{Pr}(c_{t}\neq
c^{\prime}_{t})=\mathrm{Pr}(\bar{p}_{\mathcal{M}}<_{lex}\bar{b}\bar{b}^{\prime}<_{lex}\bar{p})=p-p_{\mathcal{M}}\leq\frac{1}{5f(n)}.$

By a union bound argument, the probability that the sequences
$\bar{c}=c_{0}c_{1}\cdots c_{f(n)-1}$ and
$\bar{c}^{\prime}=c^{\prime}_{0}c^{\prime}_{1}\cdots c^{\prime}_{f(n)-1}$
generated by $\mathcal{M}$ and $\mathcal{M}^{\prime}$ differ satisfies

$\mathrm{Pr}(\bar{c}\neq\bar{c}^{\prime})\leq\frac{1}{5f(n)}f(n)=\frac{1}{5}\text{
~{}and thus~{} }\mathrm{Pr}(\bar{c}=\bar{c}^{\prime})\geq 1-\frac{1}{5}.$

Since $\mathcal{M}^{\prime}$ classifies $w$ correctly with probability at
least $\tfrac{2}{3}$, it follows that $\mathcal{M}$ classifies $w$ correctly
with probability at least
$(1-\frac{1}{5})\tfrac{2}{3}>\tfrac{8}{15}>\tfrac{1}{2}$. This probability can
be increased above $\tfrac{2}{3}$ by repeating Procedure 3 a constant number
of time and taking the majority of the decisions as output [2]. Consequently,
the devices $\mathcal{M}$, $\mathcal{M}^{\prime}$ and $\mathcal{N}$ all decide
the same language $L$, and therefore,
$L\in\mathbf{PTMA}\left[\alpha(\bar{p},\log(5f)),O(f^{3})\right]$.

Input: input $w\in\Sigma^{n}$

1 Query the advice
$\alpha(\bar{p},\log(cf))(n)=\bar{p}_{\mathcal{M}}=p_{0}p_{1}\cdots
p_{\log(5f(n))-1}$

2 for  _$t=0,1,\dots,f(n)-1$_ do

3 Draw a sequence of independent fair bits $\bar{b}:=b_{0}b_{1}\cdots
b_{\log(5f(n))-1}$

4 if  _$\bar{b} <_{lex}\bar{p}_{\mathcal{M}}$_ then $c_{t}=1$

5 else $c_{t}=0$

6 Simulate network $\mathcal{N}|_{cf(n)}$ at time $t$ with $x_{2}^{t}=c_{t}$

7

return Output of $\mathcal{N}|_{cf(n)}$ over $w$ at time step $f(n)$

Procedure 3

(ii) Let $L\in\mathbf{PTMA}[\alpha(\bar{p},\log(f)),f]$. Then, there exists
some PTM/log(A) $\mathcal{M}$ with logarithmic advice
$\alpha(\bar{p},\log(f))$ deciding $L$ in time $f$. For simplicity purposes,
let the advice of $\mathcal{M}$ be denoted by $\bar{p}=p_{0}\cdots
p_{\log(f(n))-1}$ ($\bar{p}$ is not anymore the binary expansion of $p$ from
now on). Now, consider Procedure 4 below. The first for loop computes an
estimation $\bar{p}^{\prime}$ of the advice $\bar{p}$ defined by

$\bar{p}^{\prime}=\delta_{2}^{-1}(p^{\prime})[0:\log(f(n))-1]=p^{\prime}_{0}\cdots
p^{\prime}_{\log(f(n))-1}$

where

$p^{\prime}=\frac{1}{k(n)}\sum_{i=0}^{k(n)-1}b_{i}\text{ ~{}and~{}
}k(n)=\ulcorner 10p(1-p)f^{2}(n)\urcorner\,$

and the $b_{i}$ are drawn according to a Bernouilli distribution of parameter
$p$. The second for loop computes a sequence of random choices

$\bar{c}=c_{0}\cdots c_{f(n)-1}$

using von Neumann’s trick to simulate a fair coin with a biased one [2]. The
third loop simulates the behavior of the PTM/log(A) $\mathcal{M}$ using the
alternative advice $\bar{p}^{\prime}$ and the sequence of random choices
$\bar{c}$. This procedure can clearly be simulated by some $\text{SNN}[p]$
$\mathcal{N}$ in time $O(k+2f)=O(f^{2})$, where the random samples of bits are
given by the stochastic cell and the remaining recursive instructions
simulated by a rational-weighted sub-network.

It remains to show that $\mathcal{M}$ and $\mathcal{N}$ decide the same
language $L$. For this purpose, we estimate the error probability of
$\mathcal{N}$ at deciding language $L$. First, we show that $\bar{p}^{\prime}$
is a good approximation of the advice $\bar{p}$ of $\mathcal{M}$. Note that
$\bar{p}^{\prime}\neq\bar{p}$ iff
$|p^{\prime}-p|>\tfrac{1}{2^{\log(f(n))}}=\tfrac{1}{f(n)}$. Note also that by
definition, $p^{\prime}=\tfrac{\\#1}{k(n)}$, where
$\\#1\sim\mathcal{B}(k(n),p)$ is a binomial random variable of parameters
$k(n)$ and $p$ with $\mathrm{E}(\\#1)=k(n)p$ and
$\mathrm{Var}(\\#1)=k(n)p(1-p)$. It follows that

$\displaystyle\mathrm{Pr}\left(\bar{p}^{\prime}\neq\bar{p}\right)$
$\displaystyle=$
$\displaystyle\mathrm{Pr}\left(|p^{\prime}-p|>\frac{1}{f(n)}\right)$
$\displaystyle=$
$\displaystyle\mathrm{Pr}\left(|k(n)p^{\prime}-k(n)p|>\frac{k(n)}{f(n)}\right)$
$\displaystyle=$
$\displaystyle\mathrm{Pr}\left(|\\#1-\mathrm{E}(\\#1)|>\frac{k(n)}{f(n)}\right).$

The Chebyshev’s inequality ensures that

$\mathrm{Pr}\left(\bar{p}^{\prime}\neq\bar{p}\right)\leq\frac{\mathrm{Var}(\\#1)f^{2}(n)}{k^{2}(n)}=\frac{p(1-p)f^{2}(n)}{k(n)}<\frac{1}{10}$

since $k(n)>10p(1-p)f^{2}(n)$.

We now estimate the source of error coming from the simulation of a fair coin
by a biased one in Procedure 4 (loop of Line 4). Note that at each step $i$,
if the two bits $bb^{\prime}$ are different ($01$ or $10$), then $c_{t}$ is
drawn with fair probability $\tfrac{1}{2}$, like in the case of the machine
$\mathcal{M}$. Hence, the sampling process of $\mathcal{N}$ and $\mathcal{M}$
differ in probability precisely when all of the $K$ draws produce identical
bits $bb^{\prime}$ ($00$ or $11$). The probability that the two bits
$bb^{\prime}$ are identical at step $i$ is $p^{2}+(1-p)^{2}$, and hence, the
probability that the $K=\frac{-4-\log(f(n))}{\log(p^{2}+(1-p)^{2})}$
independent draws all produce identical bits $bb^{\prime}$ satisfies

$\left(p^{2}+(1-p)^{2}\right)^{K}\leq 2^{-4-\log(f(n))}=\frac{1}{16f(n)}.$

by using the fact that $x^{1/\log(x)}\geq 2$. By a union bound argument, the
probability that some $c_{t}$ in the sequence $c_{0}\cdots c_{f(n)-1}$ is not
drawn with a fair probability $\tfrac{1}{2}$ is bounded by $\tfrac{1}{16}$.
Equivalently, the probability that all random randoms bits $c_{t}$ of the
sequence $c_{0}\cdots cs_{f(n)-1}$ are drawn with fair probability
$\tfrac{1}{2}$ is at least $\tfrac{15}{16}$.

To safely estimate the error probability of $\mathcal{N}$, we restrict
ourselves to situations when $\mathcal{M}$ and $\mathcal{N}$ behave the same,
and assume that $\mathcal{N}$ always makes errors otherwise. These situations
happen when $\mathcal{M}$ and $\mathcal{N}$ use the same advice as well as the
same fair probability for their random processes. These two events are
independent and of probability at least $\tfrac{9}{10}$ and at least
$\tfrac{15}{16}$, respectively. Hence, $\mathcal{M}$ and $\mathcal{N}$ agree
on any input $w$ with probability at least
$\tfrac{9}{10}\cdot\tfrac{15}{16}>\tfrac{4}{5}$. Consequently, the probability
that $\mathcal{N}$ decides correctly whether $w\in L$ or not is bounded by
$\tfrac{4}{5}\cdot\tfrac{2}{3}>\tfrac{1}{2}$. As before, this probability can
be made larger than $\tfrac{2}{3}$ by repeating Procedure 4 a constant number
of times and taking the majority of the decisions as output [2]. This shows
that $L(\mathcal{N})=L(\mathcal{M})=L$, and therefore
$L\in\mathbf{SNN}\left[p,O(f^{2})\right]$. ∎

Input: input $w\in\Sigma^{n}$

1 for  _$i=0,\dots,k(n):=\ulcorner 10p(1-p)f^{2}(n)\urcorner$_ do

2 Draw a random bit $b_{i}$ with probability $p$

3

4Compute the estimation of the advice of $\mathcal{M}$
$\bar{p}^{\prime}=p^{\prime}_{0}\cdots
p^{\prime}_{\log(f(n))-1}=\delta_{2}^{-1}(\frac{1}{k}\sum_{i=0}^{k(n)-1}b_{i})[0:\log(f(n))-1]$

5 for  _$t=0,\dots,f(n)-1$_ do

6 $c_{t}=0$;

7 for
_$i=0,\dots,\ulcorner\frac{-4-\log(f(n))}{\log(p^{2}+(1-p)^{2})}\urcorner$_ do

8 Draw $2$ random bits $b$ and $b^{\prime}$ with probability $p$

9 if  _$bb^{\prime}=01$_ then $c_{t}=0$; break

10 if  _$bb^{\prime}=10$_ then $c_{t}=1$; break

11

12

13for  _$t=0,\dots,f(n)-1$_ do

14 Simulate the PTM/log(A) $\mathcal{M}$ using the advice
$\bar{p}^{\prime}=p^{\prime}_{0}\cdots p^{\prime}_{\log(f(n))-1}$ and the
sequence of random choices $\bar{c}=c_{0}\cdots c_{f(n)-1}$

15

return Output of $\mathcal{M}$ over $w$ at time step $f(n)$

Procedure 4

The class of languages decided in polynomial time by stochastic networks using
real probabilities and Turing machines using related advices are the same. In
this case, however, the length of the advice are logarithmic instead of
polynomial.

######  Corollary 13.

Let $p\in\Delta$ be some real probability and $P\subseteq\Delta$ be some set
of real probabilities.

  1. (i)

$\mathbf{SNN}[p,\mathrm{poly}]=\mathbf{PTMA}[\alpha(\bar{p},\mathrm{log}),\mathrm{poly}]$.

  2. (ii)

$\mathbf{SNN}[P,\mathrm{poly}]=\mathbf{PTMA}[\alpha(\bar{P},\mathrm{log}),\mathrm{poly}]$.

###### Proof.

The proof is similar to that of Corollary 6. ∎

##  6 Hierarchies

In this section, we provide a refined characterization of the super-Turing
computational power of analog, evolving, and stochastic neural networks based
on the Kolmogorov complexity of their real weights, evolving weights, and real
probabilities, respectively. More specifically, we show the existence of
infinite hierarchies of classes of analog and evolving neural networks located
between $\mathbf{P}$ and $\mathbf{P/poly}$. We also establish the existence of
an infinite hierarchy of classes of stochastic neural networks between
$\mathbf{BPP}$ and $\mathbf{BPP/log^{*}}$. Beyond proving the existence and
providing examples of such hierarchies, we describe a generic way of
constructing them based on classes of functions of increasing complexity.

Towards this purpose, we define the Kolmogorov complexity of a real number as
stated in a related work [3]. Let $\mathcal{M}_{U}$ be a universal Turing
machine, $f,g:\mathbb{N}\rightarrow\mathbb{N}$ be two functions, and
$\alpha\in\Sigma^{\omega}$ be some infinite word. We say that
$\alpha\in\bar{K}^{f}_{g}$ if there exists $\beta\in\Sigma^{\omega}$ such
that, for all but finitely many $n$, the machine $\mathcal{M}_{U}$ with inputs
$\beta[0:m-1]$ and $n$ will output $\alpha[0:n-1]$ in time $g(n)$, for all
$m\geq f(n)$. In other words, $\alpha\in\bar{K}^{f}_{g}$ if its $n$ first bits
can be recovered from the $f(n)$ first bits of some $\beta$ in time $g(n)$.
The notion expressed its interest when $f(n)\leq n$, in which case
$\alpha\in\bar{K}^{f}_{g}$ means that every $n$-long prefix of $\alpha$ can be
compressed into and recovered from a smaller $f(n)$-long prefix of $\beta$.
Given two classes of functions $\mathcal{F}$ and $\mathcal{G}$, we define
$\bar{K}^{\mathcal{F}}_{\mathcal{G}}=\bigcup_{f\in\mathcal{F}}\bigcup_{g\in\mathcal{G}}\bar{K}^{f}_{g}$.
Finally, for any real number $r\in\Delta$ with associated binary expansion
$\bar{r}=\delta^{-1}_{4}(r)\in\Sigma^{\omega}$, we say that $r\in K^{f}_{g}$
(resp. $r\in K^{\mathcal{F}}_{\mathcal{G}}$) iff $\bar{r}\in\bar{K}^{f}_{g}$
(resp. $\bar{r}\in\bar{K}^{\mathcal{F}}_{\mathcal{G}}$).

Given some set of functions $\mathcal{F}\subseteq\mathbb{N}^{\mathbb{N}}$, we
say $\mathcal{F}$ is a class of _reasonable advice bounds_ if the following
conditions hold:

  * •

Sub-linearity: for all $f\in\mathcal{F}$, then $f(n)\leq n$ for all
$n\in\mathbb{N}$.

  * •

Dominance by a polynomially computable function: for all $f\in\mathcal{F}$,
there exists $g\in\mathcal{F}$ such that $f\leq g$ and $g$ is computable in
polynomial time.

  * •

Closure by polynomial composition on the right: For all $f\in\mathcal{F}$ and
for all $p\in\mathrm{poly}$, there exist $g\in\mathcal{F}$ such that $f\circ
p\leq g$.

For instance, $\mathrm{log}$ is a class of reasonable advice bounds. All
properties in this definition are necessary for our separation theorems. The
first and second conditions are necessary to define Kolmogorov reals
associated to advices of bounded size. The third condition comes from the fact
that RNNs can access any polynomial number of bits from their weights during
polynomial time of computation. Note that our definition is slightly weaker
than that of Balcázar et al., who further assume that the class should be
closed under $O(.)$ [3].

The following theorem relates non-uniform complexity classes, based on
polynomial time of computation $\mathbf{P}$ and reasonable advice bounds
$\mathcal{F}$, with classes of analog and evolving networks using weights
inside $K_{\mathrm{poly}}^{\mathcal{F}}$ and
$\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$, respectively.

######  Theorem 14.

Let $\mathcal{F}$ be a class of reasonable advice bounds, and let
$K_{\mathrm{poly}}^{\mathcal{F}}\subseteq\Delta$ and
$\bar{K}_{\mathrm{poly}}^{\mathcal{F}}\subseteq\Sigma^{\omega}$ be the sets of
Kolmogorov reals associated with $\mathcal{F}$. Then

$\mathbf{P}/\mathcal{F}^{*}=\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]=\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right].$

###### Proof.

We prove the first equality. By definition, $\mathbf{P}/\mathcal{F}^{*}$ is
the class of languages decided in polynomial time by some TM/A using any
possible prefix advice of length $f\in\mathcal{F}$, namely,

$\mathbf{P}/\mathcal{F}^{*}=\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)},\mathrm{poly}\right].$

In addition, Corollary 6 ensures that

$\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)},\mathrm{poly}\right].$

Hence, we need to show that

$\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)},\mathrm{poly}\right]=\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)},\mathrm{poly}\right].$
(5)

Equation 5 can be understood as follows: in polynomial time of computation,
the TM/As using small advices (of size $\mathcal{F}$) are equivalent to those
using larger but compressible advices (of size $\mathrm{poly}$ and inside
$\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$).

For the sake of simplicity, we suppose that the polynomial time of computation
of the TM/As are clear from the context by introducing the following
abbreviations:

$\displaystyle\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)},\mathrm{poly}\right]$
$\displaystyle:=$
$\displaystyle\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)}\right]$
$\displaystyle\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)},\mathrm{poly}\right]$
$\displaystyle:=$
$\displaystyle\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)}\right].$

We show the backward inclusion of Eq. (5). Let

$L\in\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)}\right].$

Then, there exists some TM/A $\mathcal{M}$ using advice
$\alpha(\bar{r},p_{1})$, where
$\bar{r}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$ and $p_{1}\in\mathrm{poly}$,
deciding $L$ in time $p_{2}\in\mathrm{poly}$. Since
$\bar{r}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$, there exist
$\beta\in\Sigma^{\omega}$, $f\in\mathcal{F}$ and $p_{3}\in\mathrm{poly}$ such
that the $p_{1}(n)$ bits of $\bar{r}$ can be computed from the $f(p_{1}(n))$
bits of $\beta$ in time $p_{3}(p_{1}(n))$. Hence, the TM/A $\mathcal{M}$ can
be simulated by the TM/A $\mathcal{M}^{\prime}$ with advice
$\alpha(\beta,f\circ p_{1})$ working as follows: on every input
$w\in\Sigma^{n}$, $\mathcal{M}^{\prime}$ first queries its advice string
$\beta_{0}\beta_{1}\cdots\beta_{f(p_{1}(n))-1}$, then reconstructs the advice
$r_{0}r_{1}\dots r_{p_{1}(n)-1}$ in time $p_{3}(p_{1}(n))$, and finally
simulates the behavior of $\mathcal{M}$ over input $w$ in real time. Clearly,
$L(\mathcal{M}^{\prime})=L(\mathcal{M})=L$. In addition, $p_{3}\circ
p_{1}\in\mathrm{poly}$, and since $\mathcal{F}$ is a class of reasonable
advice bounds, there is $g\in\mathcal{F}$ such that $f\circ p_{1}\leq g$.
Therefore,

$L\in\mathbf{TMA}\left[\alpha(\beta,g)\right]\subseteq\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)}\right].$

We now prove the forward inclusion of Eq. (5). Let

$L\in\mathbf{TMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\big{)}\right].$

Then, there exists some TM/A $\mathcal{M}$ with advice $\alpha(\bar{r},f)$,
with $\bar{r}\in\Sigma^{\omega}$ and $f\in\mathcal{F}$, deciding $L$ in time
$p_{1}\in\mathrm{poly}$. Since $\mathcal{F}$ is a class of reasonable advice
bounds, there exists $g\in\mathcal{F}$ such that $f\leq g$ and $g$ is
computable in polynomial time. We now define
$\bar{s}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$ using $\bar{r}$ and $g$ as
follows: for each $i\geq 0$, let $\bar{r}_{i}$ be the sub-word of $\bar{r}$
defined by

$\bar{r}_{i}=\begin{cases}r_{0}r_{1}\cdots r_{g(0)-1}&\text{if $i=0$}\\\
r_{g(i-1)}r_{g(i-1)+1}\cdots r_{g(i)-1}&\text{if $i>0$}\\\ \end{cases}$

and let

$\bar{s}=\bar{r}_{0}0\bar{r}_{1}0\bar{r}_{2}0\cdots.$

Given the $g(n)$ first bits of $\bar{r}$, we can build the $g(n)+n\geq n$
first bits of $\bar{s}$ by computing $g(i)$ and the corresponding block
$\bar{r}_{i}$ (which can be empty) for all $i\leq n$, and then intertwining
those with $0$’s. This process can be done in polynomial time, since $g$ is
computable is polynomial time. Therefore,
$\bar{s}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$.

Let $q(n)=2n$. Since $\mathcal{F}$ is a class of reasonable advice bounds,
$g(n)\leq n$, and thus $q(n)=2n\geq g(n)+n$. Now, consider the TM/A
$\mathcal{M}^{\prime}$ with advice $\alpha(\bar{s},q)$ working as follows. On
every input $w\in\Sigma^{n}$, the machine $\mathcal{M}^{\prime}$ first queries
its advice $\alpha(\bar{s},q)(n)=s_{0}s_{1}\cdots s_{q(n)-1}$. Then,
$\mathcal{M}^{\prime}$ reconstructs the string $r_{0}r_{1}\cdots r_{g(n)-1}$
by computing $g(i)$ and then removing $n$ $0$’s from $\alpha(\bar{s},q)(n)$ at
positions $g(i)+i$, for all $i\leq n$. This is done in polynomial time, since
$g$ is computable in polynomial time. Finally, $\mathcal{M}^{\prime}$
simulates $\mathcal{M}$ with advice $r_{0}r_{1}\cdots r_{g(n)-1}$ in real
time. Clearly, $L(\mathcal{M}^{\prime})=L(\mathcal{M})=L$. Therefore,

$L\in\mathbf{TMA}\left[\alpha(\bar{s},q)\right]\subseteq\mathbf{TMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\big{)}\right].$

The property that have just been established together with Corollary 10 proves
the second equality. ∎

We now prove the analogous of Theorem 14 for the case of probabilistic
complexity classes and machines. In this case, however, the class of advice
bounds does not anymore correspond exactly to the Kolmogorov space bounds of
the real probabilities. Instead, a logarithmic correcting factor needs to be
introduced. Given some class of functions $\mathcal{F}$, we let
$\mathcal{F}\circ\log$ denote the set $\\{f\circ\log\mid f\in\mathcal{F}\\}$.

######  Theorem 15.

Let $\mathcal{F}$ be a class of reasonable advice bounds, then

$\mathbf{BPP}/(\mathcal{F}\circ\log)^{*}=\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right].$

###### Proof.

By definition, $\mathbf{BPP}/(\mathcal{F}\circ\log)^{*}$ is the class of
languages decided by PTM/A using any possible prefix advice of length
$f\in\mathcal{F}\circ\log$:

$\mathbf{BPP}/(\mathcal{F}\circ\log)^{*}=\mathbf{PTMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\circ\log\big{)},\mathrm{poly}\right].$

Moreover, Corollary 13 ensures that

$\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]=\mathbf{PTMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{log}\big{)},\mathrm{poly}\right].$

Hence, we need to prove the following equality:

$\mathbf{PTMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{log}\big{)},\mathrm{poly}\right]=\mathbf{PTMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\circ\log\big{)},\mathrm{poly}\right]$
(6)

We first prove the forward inclusion of Eq. 6. Let

$L\in\mathbf{PTMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{log}\big{)},\mathrm{poly}\right].$

Then, there exists some PTM/A $\mathcal{M}$ using advice
$\alpha(\bar{r},c\log)$, where
$\bar{r}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$ and $c>0$, that decides $L$
in time $p_{1}\in\mathrm{poly}$. Since
$\bar{r}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$, there exist
$\beta\in\Sigma^{\omega}$ and $f\in\mathcal{F}$ such that $\bar{r}[0:n-1]$ can
be computed from $\beta[0:f(n)-1]$ in time $p_{2}(n)\in\mathrm{poly}$, for all
$n\geq 0$. Consider the PTM/A $\mathcal{M}^{\prime}$ with advice
$\alpha(\beta,f\circ c\log)$ working as follows. First, $\mathcal{M}^{\prime}$
queries its advice $\beta[0:f(c\log(n))-1]$, then it computes
$\bar{r}[0:c\log(n)-1]$ from this advice in time $p_{2}(\log(n))$, and finally
it simulates $\mathcal{M}$ with advice $\bar{r}[0:c\log(n)-1]$ in real time.
Consequently, $\mathcal{M}^{\prime}$ decides the same language $L$ as
$\mathcal{M}$, and works in time $O(p_{1}+p_{2}\circ\log)\in\mathrm{poly}$.
Therefore,

$L\in\mathbf{PTMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\circ\log\big{)},\mathrm{poly}\right].$

We now prove the backward inclusion of Eq. 6. Let

$L\in\mathbf{PTMA}\left[\alpha\big{(}\Sigma^{\omega},\mathcal{F}\circ\log\big{)},\mathrm{poly}\right].$

Then, there exists some PTM/A $\mathcal{M}$ using advice
$\alpha(\bar{r},f\circ c\log)$, where $\bar{r}\in\Sigma^{\omega}$,
$f\in\mathcal{F}$ and $c>0$, that decides $L$ in time $p_{1}\in\mathrm{poly}$.
Using the same argument as in the proof of Theorem 14, there exist
$\bar{s}\in\bar{K}_{\mathrm{poly}}^{\mathcal{F}}$ and $g\in\mathcal{F}$ such
that $f\leq g$ and the smaller word $\bar{r}[0:g(n)-1]$ can be retrieved from
the larger one $\bar{s}[0:2n-1]$ in time $p_{2}(n)\in\mathrm{poly}$, for all
$n\geq 0$. Now, consider the PTM/A $\mathcal{M}^{\prime}$ using advice
$\alpha(\bar{s},2c\log)$ and working as follows. First, $\mathcal{M}^{\prime}$
queries its advice $\bar{s}[0:2c\log(n)-1]$, then it reconstructs
$\bar{r}[0:g(c\log(n))-1]$ from this advice in time $O(p_{2}(\log(n)))$, and
finally, it simulates $\mathcal{M}$ with advice $\bar{r}[0:g(c\log(n))-1]$ in
real time. Since $\bar{r}[0:g(c\log(n))-1]$ extends
$\bar{r}[0:f(c\log(n))-1]$, $\mathcal{M}^{\prime}$ and $\mathcal{M}$ decide
the same language $L$. In addition, $\mathcal{M}^{\prime}$ works in time
$O(p_{1}+p_{2}\circ\log)\in\mathrm{poly}$. Therefore,

$\mathbf{PTMA}\left[\alpha\big{(}\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{log}\big{)},\mathrm{poly}\right].$

∎

We now prove the separation of non-uniform complexity classes of the form
$\mathcal{C}/f$. Towards this purpose, we assume that each class of languages
$\mathcal{C}$ is defined on the basis of a set of machines that decide these
languages. For the sake of simplicity, we naturally identify $\mathcal{C}$
with its associated class of machines. For instance, $\mathbf{P}$ and
$\mathbf{BPP}$ are identified with the set of Turing machines and
probabilistic Turing machines working in polynomial time, respectively. In
this context, we show that, as soon as the advice is increased by a single
bit, the capabilities of the corresponding machines are also increased. To
achieve this result, the two following weak conditions are required. First,
$\mathcal{C}$ must contain the machines capable of reading their full inputs
(of length $n$) and advices (of length $f(n)$) (otherwise, any additional
advice bit would not change anything). Hence, $\mathcal{C}$ must at least
include the machines working in time $O(n+f(n))$. Secondly, the advice length
$f(n)$ should be smaller than $2^{n}$, for otherwise, the advice could encode
any possible language, and the corresponding machine would have full power.
The following result is proven for machines with general (i.e., non-prefix)
advices, before being stated for the particular case of machines with prefix
advices.

######  Theorem 16.

Let $f,g:\mathbb{N}\rightarrow\mathbb{N}$ be two increasing functions such
that $f(n)<g(n)\leq 2^{n}$, for all $n\in\mathbb{N}$. Let $\mathcal{C}$ be a
set of machines containing the Turing machines working in time $O(n+f(n))$.
Then $\mathcal{C}/f\subsetneq\mathcal{C}/g$.

###### Proof.

Any Turing machine $M$ with advice $\alpha$ of size $f$ can be simulated by
some Turing machine $M^{\prime}$ with an advice $\alpha^{\prime}$ of size
$g>f$. Indeed, take $\alpha^{\prime}(n)=(1)^{g(n)-f(n)-1}0\alpha(n)$. Then, on
any input $w\in\Sigma^{n}$, the machine $M^{\prime}$ queries its advice
$\alpha^{\prime}(n)$, erases all $1$’s up to and including the first
encountered $0$, and then simulates $M$ with advice $\alpha(n)$. Clearly, $M$
and $M^{\prime}$ decide the same language.

To prove the strictness of the inclusion, we proceed by diagonalization.
Recall that the set of (probabilistic) Turing machines is countable. Let
$M_{0},M_{1},M_{2},\dots$ be an enumeration of the machines in $\mathcal{C}$.
For any $M_{k}\in\mathcal{C}$ and any advice
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ of size $f$, let $M_{k}/\alpha$ be
the associated (probabilistic) machine with advice, and let $L(M_{k}/\alpha)$
be its associated language. The language $L(M_{k}/\alpha)$ can be written as
the union of its sub-languages of words of length $n$, i.e.

$L(M_{k}/\alpha)=\bigcup_{n\in\mathbb{N}}L(M_{k}/\alpha)^{n}.$

For each $k,n\in\mathbb{N}$, consider the set of sub-languages of words of
length $n$ decided by $M_{k}/\alpha$, for all possible advices $\alpha$ of
size $f$, i.e.:

$\mathcal{L}^{n}_{k}=\big{\\{}L(M_{k}/\alpha)^{n}:\alpha\text{ is an advice of
size $f$}\big{\\}}.$

Since there are at most $2^{f(n)}$ advice strings of length $f(n)$, it follows
that $|\mathcal{L}^{n}_{k}|\leq 2^{f(n)}$, for all $k\in\mathbb{N}$, and in
particular, that $|\mathcal{L}^{n}_{n}|\leq 2^{f(n)}$. By working on the
diagonal $\mathcal{D}=\big{(}\mathcal{L}^{n}_{n}\big{)}_{n\in\mathbb{N}}$ of
the sequence $\big{(}\mathcal{L}^{n}_{k}\big{)}_{k,n\in\mathbb{N}}$
(illustrated in Table 1), we will build a language
$A=\bigcup_{n\in\mathbb{N}}A^{n}$ that cannot be decided by any Turing machine
in $\mathcal{C}$ with advice of size $f$, but can be decided by some Turing
machine in $\mathcal{C}$ with advice of size $g$. It follows that
$A\in(\mathcal{C}/g)\setminus(\mathcal{C}/f)$, and therefore,
$\mathcal{C}/f\subsetneq\mathcal{C}/g$.

| $0$ | $1$ | $2$ | $\cdots$ | $n$ | $\cdots$
---|---|---|---|---|---|---
$0$ | $\mathcal{L}^{0}_{0}$ | $\mathcal{L}^{1}_{0}$ | $\mathcal{L}^{2}_{0}$ | $\cdots$ | $\mathcal{L}^{n}_{0}$ | $\cdots$
$1$ | $\mathcal{L}^{0}_{1}$ | $\mathcal{L}^{1}_{1}$ | $\mathcal{L}^{2}_{1}$ | $\cdots$ | $\mathcal{L}^{n}_{1}$ | $\cdots$
$2$ | $\mathcal{L}^{0}_{2}$ | $\mathcal{L}^{1}_{2}$ | $\mathcal{L}^{2}_{2}$ | $\cdots$ | $\mathcal{L}^{n}_{2}$ | $\cdots$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\cdots$
$n$ | $\mathcal{L}^{0}_{n}$ | $\mathcal{L}^{1}_{n}$ | $\mathcal{L}^{2}_{n}$ | $\cdots$ | $\mathcal{L}^{n}_{n}$ | $\cdots$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\cdots$ | $\vdots$ | $\ddots$
Table 1: Illustration of the sequence
$\big{(}\mathcal{L}^{n}_{k}\big{)}_{k,n\in\mathbb{N}}$. Each set
$\mathcal{L}^{n}_{k}$ satisfies $|\mathcal{L}^{n}_{k}|\leq 2^{f(n)}$. The
diagonal $\mathcal{D}=\big{(}\mathcal{L}^{n}_{n}\big{)}_{n\in\mathbb{N}}$ is
highlighted.

Let $n\in\mathbb{N}$. For each $i<2^{n}$, let $b(i)\in\Sigma^{n}$ be the
binary representation of $i$ over $n$ bits. For any subset
$\mathcal{L}\subseteq\mathcal{L}^{n}_{n}$, let

$\mathcal{L}\big{(}b(i)\big{)}=\left\\{L\in\mathcal{L}:b(i)\in
L\right\\}\text{ ~{}and~{}
}\bar{\mathcal{L}}\big{(}b(i)\big{)}=\left\\{L\in\mathcal{L}:b(i)\not\in
L\right\\}.$

Consider the sequence
$(\mathcal{L}^{n}_{n,0},\dots,\mathcal{L}^{n}_{n,f(n)+1})$ of decreasing
subsets of $\mathcal{L}^{n}_{n}$ and the sequence
$(A^{n}_{0},\dots,A^{n}_{f(n)+1})$ of sub-languages of words of length $n$
defined by induction for every $0\leq i\leq f(n)$ as follows

$\displaystyle\mathcal{L}^{n}_{n,0}=\mathcal{L}^{n}_{n}\text{ ~{}and~{}
}\mathcal{L}^{n}_{n,i+1}$
$\displaystyle=\begin{cases}\mathcal{L}^{n}_{n,i}\big{(}b(i)\big{)}&\text{if
}|\mathcal{L}^{n}_{n,i}\big{(}b(i)\big{)}|<|\bar{\mathcal{L}}^{n}_{n,i}\big{(}b(i)\big{)}|\\\
\bar{\mathcal{L}}^{n}_{n,i}\big{(}b(i)\big{)}&\text{otherwise}\end{cases}$
$\displaystyle A^{n}_{0}=\emptyset\text{ ~{}and~{} }\mathcal{A}^{n}_{i+1}$
$\displaystyle=\begin{cases}\mathcal{A}^{n}_{i}\cup\\{b(i)\\}&\text{if
}|\mathcal{L}^{n}_{n,i}\big{(}b(i)\big{)}|<|\bar{\mathcal{L}}^{n}_{n,i}\big{(}b(i)\big{)}|\\\
\mathcal{A}^{n}_{i}&\text{otherwise.}\end{cases}$

This construction is illustrated in Figure 3.

Figure 3: Inductive construction of the sequences
$\big{(}\mathcal{L}^{n}_{n,i}\big{)}_{i=0}^{f(n)+1}$ and
$\big{(}A^{n}_{i}\big{)}_{i=0}^{f(n)+1}$.

Note that the $n$-bit representation $b(i)$ of $i$ is well-defined, since
$0\leq i\leq f(n)<2^{n}$. In addition, the construction ensures that
$|\mathcal{L}^{n}_{n,i+1}|\leq\frac{1}{2}|\mathcal{L}^{n}_{n,i}|$, and since
$|\mathcal{L}^{n}_{n,0}|=|\mathcal{L}^{n}_{n}|\leq 2^{f(n)}$, it follows that
$|\mathcal{L}^{n}_{n,f(n)+1}|=0$, meaning that
$\mathcal{L}^{n}_{n,f(n)+1}=\emptyset$. Furthermore, the construction also
ensure that $\mathcal{L}^{n}_{i}\subseteq\mathcal{L}^{n}_{i+1}$ and
$A^{n}_{f(n)+1}\in\mathcal{L}^{n}_{n,i}$, for all $0\leq i\leq f(n)$. Now,
towards, a contradiction, suppose that $A^{n}_{f(n)+1}\in\mathcal{L}^{n}_{n}$.
The previous properties imply that

$A^{n}_{f(n)+1}\in\bigcap_{0\leq i\leq
f(n)}\mathcal{L}^{n}_{n,i}=\mathcal{L}^{n}_{n,f(n)+1}=\emptyset$

which is a contradiction. Therefore,
$A^{n}_{f(n)+1}\not\in\mathcal{L}^{n}_{n}$, for all $n\in\mathbb{N}$.

Now, consider the language

$A=\bigcup_{n\in\mathbb{N}}A^{n}_{f(n)+1}.$

By construction, $A^{n}_{f(n)+1}$ is the set of words of length $n$ of $A$,
meaning that $A^{n}_{f(n)+1}=A^{n}$, for all $n\in\mathbb{N}$. We now show
that $A$ cannot be decided by any machine in $\mathcal{C}$ with advice of size
$f$. Towards a contradiction, suppose that $A\in\mathcal{C}/f$. Then, there
exist $M_{k}\in\mathcal{C}$ and $\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ of
size $f$ such that $L(M_{k}/\alpha)=A$. On the one hand, the definition of
$\mathcal{L}^{k}_{k}$ ensures that
$L(M_{k}/\alpha)^{k}\in\mathcal{L}^{k}_{k}$. On the other hand,
$L(M_{k}/\alpha)^{k}=A^{k}=A^{k}_{f(k)+1}\not\in\mathcal{L}^{k}_{k}$, which is
a contradiction. Therefore, $A\not\in\mathcal{C}/f$.

We now show that $A\in\mathcal{C}/g$. Consider the advice function
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ of size $g=f+1$ given by
$\alpha(n)=\alpha^{n}_{0}\alpha^{n}_{1}\cdots\alpha^{n}_{f(n)}$, where

$\alpha^{n}_{i}=\begin{cases}1&\text{if }b(i)\in A^{n}\\\
0&\text{otherwise,}\end{cases}$

for all $0\leq i\leq f(n)$. Note that the advice string $\alpha(n)$ encodes
the sub-language $A^{n}$, for all $n\in\mathbb{N}$, since the latter is a
subset of $\\{b(i):i\leq f(n)\\}$ by definition. Consider the Turing machine
with advice $M/\alpha$ which, on every input $w=w_{0}w_{1}\cdots w_{n-1}$ of
length $n$, moves its advice head up to the $i$-th bit $\alpha^{n}_{i}$ of
$\alpha(n)$, where $i=b^{-1}(w)$, if this bit exists (note that $i<2^{n}$ and
$|\alpha(n)|=f(n)+1$), and accepts $w$ if and only if $\alpha^{n}_{i}=1$. Note
that these instructions can be computed in time $O(f(n)+n)$. In particular,
moving the advice head up to the $i$-th bit of $\alpha(n)$ does not require to
compute $i=b^{-1}(w)$ explicitly, but can be achieved by moving simultaneously
the input head from the end of the input to the beginning and the advice head
from left to right, in a suitable way. It follows that

$w\in L(M/\alpha)^{n}\text{ ~{}iff~{} }\alpha^{n}_{b^{-1}(w)}=1\text{
~{}iff~{} }b(b^{-1}(w))\in A^{n}\text{ ~{}iff~{} }w\in A^{n}.$

Hence, $L(M/\alpha)^{n}=A^{n}$, for all $n\in\mathbb{N}$, and thus

$L(M/\alpha)=\bigcup_{n\in\mathbb{N}}L(M/\alpha)^{n}=\bigcup_{n\in\mathbb{N}}A^{n}=A.$

Therefore, $A\in\mathcal{C}/g$. The argument can be generalized in a
straightforward way to any advice size $g$ such that $f(n)+1\leq g(n)\leq
2^{n}$.

Finally, the two properties $A\not\in\mathcal{C}/f$ and $A\in\mathcal{C}/g$
imply that $\mathcal{C}/f\subsetneq\mathcal{C}/g$. ∎

We now prove the analogous of Theorem 16 for the case of machines with prefix
advice. In this case, however, a stronger condition on the advice lengths $f$
and $g$ is required: $f\in o(g)$ instead of $f\leq g$.

######  Theorem 17.

Let $f,g:\mathbb{N}\rightarrow\mathbb{N}$ be two increasing functions such
that $f\in o(g)$ and $\lim_{n\rightarrow\infty}g(n)=+\infty$. Let
$\mathcal{C}$ be a set of machines containing the Turing machines working in
time $O(n+f(n))$. Then $\mathcal{C}/f^{*}\subsetneq\mathcal{C}/g^{*}$.

###### Proof.

The proof is similar to that of Theorem 16, except that we will construct the
language $A$ on the basis of a sequence of integers
$(n_{i})_{i\in\mathbb{N}}$. Consider the sequence $(n_{i})_{i\in\mathbb{N}}$
defined for all $i\geq 0$ as follows

$\displaystyle n_{0}$ $\displaystyle=$
$\displaystyle\min\left\\{n\in\mathbb{N}:2(f(n)+1)\leq g(n)\right\\}$
$\displaystyle n_{i+1}$ $\displaystyle=$
$\displaystyle\min\Big{\\{}n\in\mathbb{N}:2\sum_{j=0}^{i}(f(n_{j})+1)+2(f(n)+1)\leq
g(n)\Big{\\}}.$

We show by induction that the sequence $(n_{i})_{i\in\mathbb{N}}$ is well-
defined. Since $f\in o(g)$ and $\lim_{n\rightarrow\infty}g(n)=+\infty$, the
following limits hold

$\displaystyle\lim_{n\rightarrow\infty}\frac{2(f(n)+1)}{g(n)}$
$\displaystyle=$ $\displaystyle
2\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}+\lim_{n\rightarrow\infty}\frac{2}{g(n)}=0$
$\displaystyle\lim_{n\rightarrow\infty}\frac{2\sum_{j=0}^{i}(f(n_{j})+1)+2(f(n)+1)}{g(n)}$
$\displaystyle=$ $\displaystyle
2\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}+\lim_{n\rightarrow\infty}\frac{C+2}{g(n)}=0$

where $C=2\sum_{j=0}^{i}(f(n_{j})+1)$, which ensure that $n_{0}$ and $n_{i+1}$
are well-defined.

For each $k,i\in\mathbb{N}$, consider the set of sub-languages of words of
length $n_{i}$ decided by the machine $M_{k}\in\mathcal{C}$ using any possible
advice $\alpha$ of size $f$, i.e.,

$\mathcal{L}^{n_{i}}_{k}=\left\\{L(M_{k}/\alpha)^{n_{i}}:\alpha\text{ is an
advice of size $f$}\right\\}.$

Consider the diagonal
$\mathcal{D}=\big{(}\mathcal{L}^{n_{i}}_{i}\big{)}_{i\in\mathbb{N}}$ of the
set $\big{(}\mathcal{L}^{n_{i}}_{k}\big{)}_{k,n_{i}\in\mathbb{N}}$. Since
there are at most $2^{f(n_{i})}$ advice strings of length $f(n_{i})$, it
follows that $|\mathcal{L}^{n_{i}}_{i}|\leq 2^{f(n_{i})}$. Using a similar
construction as in the proof of Theorem 16, we can define by induction a sub-
language $A^{n_{i}}_{f(n_{i})+1}\subseteq\Sigma^{n_{i}}$ such that
$A^{n_{i}}_{f(n_{i})+1}\not\in\mathcal{L}^{n_{i}}_{i}$. Then, consider the
language

$A=\bigcup_{i\in\mathbb{N}}A^{n_{i}}_{f(n_{i})+1}=\bigcup_{i\in\mathbb{N}}A^{n_{i}}.$

Once again, a similar argument as in the proof of Theorem 16 ensures that
$A\not\in\mathcal{C}/f$. Since $\mathcal{C}/f^{*}\subseteq\mathcal{C}/f$, it
follows that $A\not\in\mathcal{C}/f^{*}$.

We now show that $A\in\mathcal{C}/g^{*}$. Recall that, by construction,
$A^{n_{i}}\subseteq\\{b(j):0\leq j\leq f(n_{i})\\}$. Consider the word
homomorphism $h:\Sigma^{*}\rightarrow\Sigma^{*}$ induced by the mapping
$0\mapsto 00$ and $1\mapsto 11$, and define the symbol $\\#=01$. For each
$i\in\mathbb{N}$, consider the encoding
$\beta^{n_{i}}_{0}\beta^{n_{i}}_{1}\cdots\beta^{n_{i}}_{f(n_{i})}$ of
$A^{n_{i}}$ given by

$\beta^{n_{i}}_{j}=\begin{cases}1&\text{if }b(j)\in A^{n_{i}},\\\
0&\text{otherwise,}\end{cases}$

for all $0\leq j\leq f(n_{i})$, and let
$\beta(n_{i})=h(\beta^{n_{i}}_{0}\beta^{n_{i}}_{1}\cdots\beta^{n_{i}}_{f(n_{i})})$.
Note that $|\beta(n_{i})|=2(f(n_{i})+1)$. Now, consider the advice function
$\alpha:\mathbb{N}\rightarrow\Sigma^{*}$ given by the concatenation of the
encodings of the successive $A^{n_{i}}$ separated by symbols $\\#$. Formally,

$\alpha(n)=\begin{cases}\beta(n_{0})\\#\beta(n_{1})\\#\cdots\\#\beta(n_{i})&\text{
if $n=n_{i}$ for some $i\geq 0$}\\\
\beta(n_{0})\\#\beta(n_{1})\\#\cdots\\#\beta(n_{i})\\#&\text{ if
$n_{i}<n<n_{i+1}$}.\end{cases}$

Note that $|\alpha(n)|=2\sum_{j=0}^{i}(f(n_{i})+1)\leq g(n_{i})\leq g(n)$ for
$n_{i}\leq n<n_{i+1}$, and that $\alpha$ satisfies the prefix property: $m\leq
n$ implies $|\alpha(m)|\leq|\alpha(n)|$. If necessary, the advice strings can
be extended by dummy symbols $10$ in order to achieve the equality
$|\alpha(n)|=g(n)$, for all $n\geq 0$ (assuming without loss of generality
that $g(n)$ is even). Now, consider the machine with advice $M/\alpha$ which,
on every input $w$ of length $n$, first reads its advice string $\alpha(n)$ up
to the end. If the last symbol of $\alpha(n)$ is $\\#$, then it means that
$|w|\neq n_{i}$ for all $i\geq 0$, and the machine rejects $w$. Otherwise, the
input is of length $n_{i}$ for some $i\geq 0$. Hence, the machine moves its
advice head back up to the last $\\#$ symbol, and then moves one step to the
right. At this point, the advice head points at the beginning of the advice
substring $\beta(n_{i})$. Then, the machine decodes
$\beta^{n_{i}}_{0}\beta^{n_{i}}_{1}\cdots\beta^{n_{i}}_{f(n_{i})}$ from
$\beta(n_{i})$ by removing one out of two bits. Next, as in the proof of
Theorem 16, the machine moves its advice head up to the $j$-th bit
$\beta^{n_{i}}_{j}$, where $j=b^{-1}(w)$, if this bit exists (note that
$j<2^{n_{i}}$ and $|\beta(n_{i})|=f(n_{i})+1$), and accepts $w$ if and only if
$\beta^{n_{i}}_{j}=1$. These instructions can be computed in time
$O(2\sum_{j=0}^{i}(f(n_{j})+1)+{n_{i}})$. It follows that $w\in
L(M/\alpha)^{n_{i}}$ iff $w\in A^{n_{i}}$. Thus
$L(M/\alpha)^{n_{i}}=A^{n_{i}}$, for all $i\in\mathbb{N}$, and hence

$L(M/\alpha)=\bigcup_{i\in\mathbb{N}}L(M/\alpha)^{n_{i}}=\bigcup_{i\in\mathbb{N}}A^{n_{i}}=A$

Therefore, $A\in\mathcal{C}/g^{*}$.

Finally, the two properties $A\not\in\mathcal{C}/f^{*}$ and
$A\in\mathcal{C}/g^{*}$ imply that
$\mathcal{C}/f^{*}\subsetneq\mathcal{C}/g^{*}$. ∎

The separability between classes of analog, evolving, and stochastic recurrent
neural networks using real weights, evolving weights, and probabilities of
different Kolmogorov complexities, respectively, can now be obtained.

######  Corollary 18.

Let $\mathcal{F}$ and $\mathcal{G}$ be two classes of reasonable advice bounds
such that, there is a $g\in\mathcal{G}$, such that for every
$f\in\mathcal{F}$, $f\in o(g)$ and
$\underset{n\rightarrow\infty}{\lim}g(n)=+\infty$. Then

  1. (i)

$\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]\subsetneq\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right]$

  2. (ii)

$\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]\subsetneq\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right]$

  3. (iii)

$\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]\subsetneq\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right]$

###### Proof.

(i) and (ii): Theorem 14 shows that

$\displaystyle\mathbf{P}/\mathcal{F}^{*}$ $\displaystyle=$
$\displaystyle\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]=\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]\text{
~{}and~{} }$ $\displaystyle\mathbf{P}/\mathcal{G}^{*}$ $\displaystyle=$
$\displaystyle\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right]=\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right].$

In addition, Theorem 17 ensures that

$\displaystyle\mathbf{P}/\mathcal{F}^{*}\subsetneq\mathbf{P}/\mathcal{G}^{*}$

The strict inclusions of Points (i) and (ii) directly follow.

(iii): Theorem 15 states that

$\displaystyle\mathbf{BPP}/(\mathcal{F}\circ\log)^{*}$ $\displaystyle=$
$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}},\mathrm{poly}\right]$
$\displaystyle\mathbf{BPP}/(\mathcal{G}\circ\log)^{*}$ $\displaystyle=$
$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{G}},\mathrm{poly}\right].$

In addition, note that if $f\in\mathcal{F}$ and $g\in\mathcal{G}$ satisfy the
hypotheses of Theorem 17, then so do $f\circ l\in\mathcal{F}\circ\log$ and
$g\circ l\in\mathcal{G}\circ\log$, for all $l\in\log$. Hence, Theorem 17
ensures that

$\displaystyle\mathbf{BPP}/(\mathcal{F}\circ\log)^{*}\subsetneq\mathbf{BPP}/(\mathcal{G}\circ\log)^{*}.$

The strict inclusion of Point (iii) ensues. ∎

Finally, Corollary 18 provides a way to construct infinite hierarchies of
classes of analog, evolving and stochastic neural networks based on the
Kolmogorov complexity of their underlying weights and probabilities,
respectively. The hierarchies of analog and evolving networks are located
between $\mathbf{P}$ and $\mathbf{P/poly}$. Those of stochastic networks lie
between $\mathbf{BPP}$ and $\mathbf{BPP/log^{*}}$.

For instance, define $\mathcal{F}_{i}=O\left(\log(n)^{i}\right)$, for all
$i\in\mathbb{N}$. Each $\mathcal{F}_{i}$ satisfies the three conditions for
being a class of reasonable advice bounds (note that the sub-linearity
$\log(n)^{i}$ is satisfied for $n$ sufficiently large). By Corollary 18, the
sequence of classes $(\mathcal{F}_{i})_{i\in\mathbb{N}}$ induces the following
infinite strict hierarchies of classes of neural networks:

$\displaystyle\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{0}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{1}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{ANN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{2}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$ $\displaystyle\cdots$
$\displaystyle\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}_{0}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}_{1}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{ENN}\left[\bar{K}_{\mathrm{poly}}^{\mathcal{F}_{2}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$ $\displaystyle\cdots$
$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{0}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{1}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$
$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{2}},\mathrm{poly}\right]$
$\displaystyle\subsetneq$ $\displaystyle\cdots$

We provide another example of hierarchy for stochastic networks only. In this
case, it can be noticed that the third condition for being a class of
reasonable advice bounds can be relaxed: we only need that
$\mathcal{F}\circ\log$ is a class of reasonable advice bounds and that the
functions of $\mathcal{F}$ are bounded by $n$. Accordingly, consider some
infinite sequence of rational numbers $(q_{i})_{i\in\mathbb{N}}$ such that
$0<q_{i}<1$ and $q_{i}<q_{i+1}$, for all $i\in\mathbb{N}$, and define
$\mathcal{F}_{i}=O(n^{q_{i}})$, for all $i\in\mathbb{N}$. Each
$\mathcal{F}_{i}$ satisfies the required conditions. By Corollary 18, the
sequence of classes $(\mathcal{F}_{i})_{i\in\mathbb{N}}$ induces the following
infinite strict hierarchies of classes of neural networks:

$\displaystyle\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{0}},\mathrm{poly}\right]~{}\subsetneq~{}\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{1}},\mathrm{poly}\right]~{}\subsetneq~{}\mathbf{SNN}\left[K_{\mathrm{poly}}^{\mathcal{F}_{2}},\mathrm{poly}\right]~{}\subsetneq~{}\cdots$

##  7 Conclusion

We provided a refined characterization of the super-Turing computational power
of analog, evolving, and stochastic recurrent neural networks based on the
Kolmogorov complexity of their underlying real weights, rational weights, and
real probabilities, respectively. For the two former models, infinite
hierarchies of classes of analog and evolving networks lying between
$\mathbf{P}$ and $\mathbf{P/poly}$ have been obtained. For the latter model,
an infinite hierarchy of classes of stochastic networks located between
$\mathbf{BPP}$ and $\mathbf{BPP/log^{*}}$ has been achieved. Beyond proving
the existence and providing examples of such hierarchies, Corollary 18
establishes a generic way of constructing them based on classes of functions
satisfying the reasonable advice bounds conditions.

This work is an extension of the study from Balcázar et al. [3] about a
Kolmogorov-based hierarchization of analog neural networks. In particular, the
proof of Theorem 14 draws heavily on their Theorem 6.2 [3]. In our paper
however, we adopted a relatively different approach guided by the intention of
keeping the computational relationships between recurrent neural networks and
Turing machines with advice as explicit as possible. In this regard,
Propositions 5, 9 and 12 characterize precisely the connections between the
real weights, evolving weights, or real probabilities of the networks, and the
advices of different lengths of the corresponding Turing machines. On the
contrary, the study of Balcázar et al. keeps these relationships somewhat
hidden, by referring to an alternative model of computation: the Turing
machines with tally oracles. Another difference between the two works is that
our separability results (Theorem 16 and 17) are achieved by means of a
diagonalization argument holding for any non-uniform complexity classes, which
is a result of specific interest per se. In particular, our method does not
rely on the existence of reals of high Kolmogorov complexity. A last
difference is that our conditions for classes of reasonable advice bounds are
slightly weaker than theirs.

The computational equivalence between stochastic neural networks and Turing
machines with advice relies on the results from Siegelmann [85]. Our
Proposition 12 is fairly inspired by their Lemma 6.3 [85]. Yet once again,
while their latter Lemma concerns the computational equivalence between two
models of bounded error Turing machines, our Proposition 12 describes the
explicit relationship between stochastic neural networks and Turing machines
with logarithmic advice. Less importantly, our appeal to union bound arguments
allows for technical simplifications of the arguments presented in their
Lemma.

The main message conveyed by our study is twofold: (1) the complexity of the
real or evolving weights does matter for the computational power of analog and
evolving neural networks; (2) the complexity of the source of randomness does
also play a role in the capabilities of stochastic neural networks. These
theoretical considerations contrast with the practical research path about
approximate computing, which concerns the plethora of approximation techniques
– among which precision scaling – that could sometimes lead to
disproportionate gains in efficiency of the models [66]. In our context, the
less compressible the weights or the source of stochasticity, the more
information they contain, and in turn, the more powerful the neural networks
employing them.

For future work, hierarchies based on different notions than the Kolmogorov
complexity could be envisioned. In addition, the computational universality of
echo state networks could be studied from a probabilistic perspective. Given
some echo state network $\mathcal{N}$ complying with well-suited conditions on
its reservoir, and given some computable function $f$, is it possible to find
output weights such that $\mathcal{N}$ computes like $f$ with high
probability?

Finally, the proposed study intends to bridge some gaps and present a unified
view of the refined capabilities of analog, evolving and stochastic recurrent
neural networks. The debatable question of the exploitability of the super-
Turing computational power of neural networks lies beyond the scope of this
paper, and fits within the philosophical approach to hypercomputation [84, 22,
23]. Nevertheless, we believe that the proposed study could contribute to the
progress of analog computation [5].

## Acknowledgements

This research was partially supported by Czech Science Foundation, grant
AppNeCo #GA22-02067S, institutional support RVO: 67985807.

## References

  * [1] Noga Alon, Alexander K. Dewdney, and Teunis J. Ott.  Efficient simulation of finite automata by neural nets.  J. ACM, 38(2):495–514, 1991.
  * [2] S. Arora and B. Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 2006.
  * [3] José L. Balcázar, Ricard Gavaldà, and Hava T. Siegelmann.  Computational power of neural networks: a characterization in terms of kolmogorov complexity.  IEEE Transactions on Information Theory, 43(4):1175–1183, 1997\.
  * [4] Asa Ben-Hur, Alexander Roitershtein, and Hava T. Siegelmann.  On probabilistic analog automata.  Theor. Comput. Sci., 320(2-3):449–464, 2004.
  * [5] Olivier Bournez and Amaury Pouly.  A Survey on Analog Models of Computation, pages 173–226.  Springer International Publishing, Cham, 2021.
  * [6] Jérémie Cabessa and Jacques Duparc.  Expressive power of non-deterministic evolving recurrent neural networks in terms of their attractor dynamics.  In Cristian S. Calude and Michael J. Dinneen, editors, Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings, volume 9252 of LNCS, pages 144–156. Springer, 2015.
  * [7] Jérémie Cabessa and Jacques Duparc.  Expressive power of nondeterministic recurrent neural networks in terms of their attractor dynamics.  IJUC, 12(1):25–50, 2016.
  * [8] Jérémie Cabessa and Olivier Finkel.  Expressive power of evolving neural networks working on infinite input streams.  In Fundamentals of Computation Theory - 21th International Symposium, FCT 2017, Bordeaux, Fance, September 11-13, 2017, Proceedings, Lecture Notes in Computer Science, pages Accepted, to appear. Springer, 2017.
  * [9] Jérémie Cabessa and Olivier Finkel.  Computational capabilities of analog and evolving neural networks over infinite input streams.  J. Comput. Syst. Sci., 101:86–99, 2019.
  * [10] Jérémie Cabessa and Hava T. Siegelmann.  Evolving recurrent neural networks are super-Turing.  In Proceedings of IJCNN 2011, pages 3200–3206. IEEE, 2011.
  * [11] Jérémie Cabessa and Hava T. Siegelmann.  The computational power of interactive recurrent neural networks.  Neural Computation, 24(4):996–1019, 2012.
  * [12] Jérémie Cabessa and Hava T. Siegelmann.  The super-Turing computational power of plastic recurrent neural networks.  Int. J. Neural Syst., 24(8), 2014.
  * [13] Jérémie Cabessa and Alessandro E. P. Villa.  The expressive power of analog recurrent neural networks on infinite input streams.  Theor. Comput. Sci., 436:23–34, 2012.
  * [14] Jérémie Cabessa and Alessandro E. P. Villa.  The super-Turing computational power of interactive evolving recurrent neural networks.  In Valeri Mladenov et al., editor, Proceedings of ICANN 2013, volume 8131 of LNCS, pages 58–65. Springer, 2013.
  * [15] Jérémie Cabessa and Alessandro E. P. Villa.  An attractor-based complexity measurement for boolean recurrent neural networks.  PLoS ONE, 9(4):e94204+, 2014.
  * [16] Jérémie Cabessa and Alessandro E. P. Villa.  Interactive evolving recurrent neural networks are super-Turing universal.  In Stefan Wermter et al., editor, Proceedings of ICANN 2014, volume 8681 of LNCS, pages 57–64. Springer, 2014.
  * [17] Jérémie Cabessa and Alessandro E. P. Villa.  Computational capabilities of recurrent neural networks based on their attractor dynamics.  In 2015 International Joint Conference on Neural Networks, IJCNN 2015, Killarney, Ireland, July 12-17, 2015, pages 1–8. IEEE, 2015\.
  * [18] Jérémie Cabessa and Alessandro E. P. Villa.  Expressive power of first-order recurrent neural networks determined by their attractor dynamics.  Journal of Computer and System Sciences, 82(8):1232–1250, 2016\.
  * [19] Cristian Calude and Gheorghe Paun.  Bio-steps beyond Turing.  BioSystems, 77:175–194, 2004.
  * [20] Patricia S. Churchland and Terrence J. Sejnowski.  The Computational Brain.  The MIT Press, 11 2016.
  * [21] Axel Cleeremans, David Servan-Schreiber, and James L. McClelland.  Finite state automata and simple recurrent networks.  Neural Computation, 1(3):372–381, 1989.
  * [22] B. Jack Copeland.  Hypercomputation.  Minds Mach., 12(4):461–502, 2002.
  * [23] B. Jack Copeland.  Hypercomputation: philosophical issues.  Theor. Comput. Sci., 317(1-3):251–267, 2004.
  * [24] Stanley Franklin and Max Garzon.  Neural computability.  In Omid Omidvar, editor, Progress in Neural Networks, pages 128–144. Ablex, Norwood, NJ, USA, 1989.
  * [25] Max Garzon and Stanley Franklin.  Neural computability II.  In Omid Omidvar, editor, Proceedings of the Third International Joint Conference on Neural Networks, pages 631–637. IEEE, 1989.
  * [26] Marian Gheorghe and Mike Stannett.  Membrane system models for super-Turing paradigms.  Natural Computing, 11(2):253–259, 2012.
  * [27] Lukas Gonon and Juan-Pablo Ortega.  Reservoir computing universality with stochastic inputs.  IEEE Trans. Neural Networks Learn. Syst., 31(1):100–112, 2020\.
  * [28] Lukas Gonon and Juan-Pablo Ortega.  Fading memory echo state networks are universal.  Neural Networks, 138:10–13, 2021.
  * [29] K. Greff, R. K. Srivastava, J. Koutnìk, B. R. Steunebrink, and J. Schmidhuber.  LSTM: A search space odyssey.  IEEE Transactions on Neural Networks and Learning Systems, 28(10):2222–2232, 2017.
  * [30] Lyudmila Grigoryeva and Juan-Pablo Ortega.  Echo state networks are universal.  Neural Networks, 108:495–508, 2018.
  * [31] Lyudmila Grigoryeva and Juan-Pablo Ortega.  Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systems.  J. Mach. Learn. Res., 19:24:1–24:40, 2018.
  * [32] Ralph Hartley and Harold Szu.  A comparison of the computational power of neural network models.  In Charles Butler, editor, Proceedings of the IEEE First International Conference on Neural Networks, pages 17–22. IEEE, 1987.
  * [33] Donald O. Hebb.  The organization of behavior : a neuropsychological theory.  John Wiley & Sons Inc., 1949.
  * [34] Bill G. Horne and Don R. Hush.  Bounds on the complexity of recurrent neural network implementations of finite state machines.  Neural Networks, 9(2):243–252, 1996.
  * [35] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  Neural Networks, 4(2):251–257, 1991.
  * [36] Kurt Hornik, Maxwell Stinchcombe, and Halber White.  Multilayer feedforward networks are universal approximators.  Neural Networks, 2(5):359–366, 1989.
  * [37] Heikki Hyötyniemi.  Turing machines are recurrent neural networks.  In J. Alander, T. Honkela, and Jakobsson M., editors, STeP ’96 - Genes, Nets and Symbols; Finnish Artificial Intelligence Conference, Vaasa 20–23 Aug. 1996, pages 13–24, Vaasa, Finland, 1996. University of Vaasa, Finnish Artificial Intelligence Society (FAIS).  STeP ’96 - Genes, Nets and Symbols; Finnish Artificial Intelligence Conference, Vaasa, Finland, 20-23 August 1996.
  * [38] Piotr Indyk.  Optimal simulation of automata by neural nets.  In STACS, pages 337–348, 1995.
  * [39] Mihai Ionescu, Gheorghe Păun, and Takashi Yokomori.  Spiking neural P systems.  Fundam. Inform., 71(2-3):279–308, 2006.
  * [40] H. Jaeger.  Short term memory in echo state networks.  GMD-Report 152, GMD - German National Research Institute for Computer Science, 2002.
  * [41] Herbert Jaeger.  The “echo state” approach to analysing and training recurrent neural networks.  GMD Report 148, GMD - German National Research Institute for Computer Science, 2001.
  * [42] Herbert Jaeger and Harald Haas.  Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication.  Science, 304(5667):78–80, 2004.
  * [43] Joe Kilian and Hava T. Siegelmann.  The dynamic universality of sigmoidal neural networks.  Inf. Comput., 128(1):48–56, 1996.
  * [44] Stephen C. Kleene.  Representation of events in nerve nets and finite automata.  In Claude Shannon and John McCarthy, editors, Automata Studies, pages 3–41. Princeton University Press, Princeton, NJ, 1956.
  * [45] Stefan C. Kremer.  On the computational power of elman-style recurrent networks.  Neural Networks, IEEE Transactions on, 6(4):1000–1004, 1995.
  * [46] Mantas Lukoševičius and Herbert Jaeger.  Reservoir computing approaches to recurrent neural network training.  Computer Science Review, 3(3):127–149, 2009.
  * [47] Wolfgang Maass.  On the computational complexity of networks of spiking neurons.  In Gerald Tesauro, David S. Touretzky, and Todd K. Leen, editors, Advances in Neural Information Processing Systems 7, NIPS Conference, Denver, CO, USA, 1994, pages 183–190. MIT Press, 1994.
  * [48] Wolfgang Maass.  On the computational power of noisy spiking neurons.  In David S. Touretzky, Michael Mozer, and Michael E. Hasselmo, editors, Advances in Neural Information Processing Systems 8, NIPS Conference, Denver, CO, November 27-30, 1995, pages 211–217. MIT Press, 1995\.
  * [49] Wolfgang Maass.  Lower bounds for the computational power of networks of spiking neurons.  Neural Computation, 8(1):1–40, 1996.
  * [50] Wolfgang Maass.  Noisy spiking neurons with temporal coding have more computational power than sigmoidal neurons.  In Michael Mozer, Michael I. Jordan, and Thomas Petsche, editors, Advances in Neural Information Processing Systems 9, NIPS Conference, Denver, CO, USA, December 2-5, 1996, pages 211–217. MIT Press, 1996.
  * [51] Wolfgang Maass.  Fast sigmoidal networks via spiking neurons.  Neural Computation, 9(2):279–304, 1997.
  * [52] Wolfgang Maass.  Networks of spiking neurons: The third generation of neural network models.  Neural Networks, 10(9):1659–1671, 1997.
  * [53] Wolfgang Maass.  Models for fast analog computation with spiking neurons.  In Shiro Usui and Takashi Omori, editors, The Fifth International Conference on Neural Information Processing, ICONIP’R Conference, Kitakyushu, Japan, October 21-23, 1998, Proceedings, pages 187–188. IOA Press, 1998.
  * [54] Wolfgang Maass.  Computing with spiking neurons.  In Wolfgang Maass and Christopher M. Bishop, editors, Pulsed Neural Networks, pages 55–85. MIT Press, Cambridge, MA, USA, 1999.
  * [55] Wolfgang Maass and Christopher M. Bishop, editors.  Pulsed Neural Networks.  MIT Press, Cambridge, MA, USA, 1999.
  * [56] Wolfgang Maass and Henry Markram.  On the computational power of circuits of spiking neurons.  J. Comput. Syst. Sci., 69(4):593–616, 2004.
  * [57] Wolfgang Maass and Pekka Orponen.  On the effect of analog noise in discrete-time analog computations.  Neural Comput., 10(5):1071–1095, 1998.
  * [58] Wolfgang Maass and Berthold Ruf.  On computations with pulses.  Inf. Comput., 148(2):202–218, 1999.
  * [59] Wolfgang Maass and Michael Schmitt.  On the complexity of learning for a spiking neuron (extended abstract).  In Yoav Freund and Robert E. Schapire, editors, Proceedings of the Tenth Annual Conference on Computational Learning Theory, COLT Conference, Nashville, TN, USA, July 6-9, 1997, pages 54–61. ACM, 1997.
  * [60] Wolfgang Maass and Michael Schmitt.  On the complexity of learning for spiking neurons with temporal coding.  Inf. Comput., 153(1):26–46, 1999.
  * [61] Wolfgang Maass and Eduardo D. Sontag.  Analog neural nets with gaussian or other common noise distributions cannot recognize arbitary regular languages.  Neural Comput., 11(3):771–782, 1999.
  * [62] Warren S. McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  Bulletin of Mathematical Biophysic, 5:115–133, 1943.
  * [63] William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav.  A formal hierarchy of RNN architectures.  In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pages 443–459. Association for Computational Linguistics, 2020.
  * [64] Marvin L. Minsky.  Computation: finite and infinite machines.  Prentice-Hall, Inc., Englewood Cliffs, N. J., 1967.
  * [65] Marvin L. Minsky and Seymour Papert.  Perceptrons: An Introduction to Computational Geometry.  MIT Press, Cambridge, MA, USA, 1969.
  * [66] Sparsh Mittal.  A survey of techniques for approximate computing.  48(4), mar 2016.
  * [67] João Pedro Guerreiro Neto, Hava T. Siegelmann, José Félix Costa, and Carmen Paz Suárez Araujo.  Turing universality of neural nets (revisited).  In Franz Pichler and Roberto Moreno-Díaz, editors, Computer Aided Systems Theory - EUROCAST’97, A Selection of Papers from the 6th International Workshop on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Spain, February 24-28, 1997, Proceedings, volume 1333 of Lecture Notes in Computer Science, pages 361–366. Springer, 1997.
  * [68] John von Neumann.  The computer and the brain.  Yale University Press, New Haven, CT, USA, 1958.
  * [69] Christian W. Omlin and C. Lee Giles.  Constructing deterministic finite-state automata in recurrent neural networks.  J. ACM, 43(6):937–972, 1996.
  * [70] Gheorghe Păun.  Membrane Computing. An Introduction.  Springer-Verlag, Berlin, 2002.
  * [71] Jordan B. Pollack.  On Connectionist Models of Natural Language Processing.  PhD thesis, Computing Reseach Laboratory, New Mexico State University, Las Cruces, NM, 1987.
  * [72] Gheorghe Păun.  Computing with membranes.  J. Comput. Syst. Sci., 61(1):108–143, 2000.
  * [73] Gheorghe Păun.  Spiking neural P systems: A tutorial.  Bulletin of the EATCS, 91:145–159, 2007.
  * [74] Gheorghe Păun.  Bibliography of spiking neural P systems.  Natural Computing, 7(4):551–553, 2008.
  * [75] Gheorghe Păun, Mario J. Pérez-Jiménez, and Grzegorz Rozenberg.  Spike trains in spiking neural P systems.  Int. J. Found. Comput. Sci., 17(4):975–1002, 2006.
  * [76] Gheorghe Păun, Mario J. Pérez-Jiménez, and Arto Salomaa.  Spiking neural P systems: an early survey.  Int. J. Found. Comput. Sci., 18(3):435–455, 2007.
  * [77] Frank Rosenblatt.  The perceptron: A perceiving and recognizing automaton.  Technical Report 85-460-1, Cornell Aeronautical Laboratory, Ithaca, New York, 1957.
  * [78] Frank Rosenblatt.  The perceptron: A probabilistic model for information storage and organization in the brain.  Psychological Review, 65(6):386–408, 1958.
  * [79] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning representations by back-propagating errors.  Nature, 323:533–536, 1986.
  * [80] Jürgen Schmidhuber.  Dynamische neuronale Netze und das fundamentale raumzeitliche Lernproblem (Dynamic neural nets and the fundamental spatio-temporal credit assignment problem).  PhD thesis, Institut für Informatik, Technische Universität München, 1990.
  * [81] Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural Networks, 61:85–117, 2015.
  * [82] Hava T. Siegelmann.  Computation beyond the Turing limit.  Science, 268(5210):545–548, 1995.
  * [83] Hava T. Siegelmann.  Recurrent neural networks and finite automata.  Computational Intelligence, 12:567–574, 1996.
  * [84] Hava T. Siegelmann.  Neural networks and analog computation: beyond the Turing limit.  Birkhauser Boston Inc., Cambridge, MA, USA, 1999.
  * [85] Hava T. Siegelmann.  Stochastic analog networks and computational complexity.  J. Complexity, 15(4):451–475, 1999.
  * [86] Hava T. Siegelmann.  Neural and super-Turing computing.  Minds Mach., 13(1):103–114, 2003.
  * [87] Hava T. Siegelmann and Eduardo D. Sontag.  Analog computation via neural networks.  Theor. Comput. Sci., 131(2):331–360, 1994.
  * [88] Hava T. Siegelmann and Eduardo D. Sontag.  On the computational power of neural nets.  J. Comput. Syst. Sci., 50(1):132–150, 1995.
  * [89] Alan M. Turing.  Intelligent machinery.  Technical report, National Physical Laboratory, Teddington, UK, 1948.
  * [90] Jiří Šíma.  Subrecursive neural networks.  Neural Networks, 116:208–223, 2019.
  * [91] Jiří Šíma.  Analog neuron hierarchy.  Neural Networks, 128:199–215, 2020.