<p>After many years, let me give an answer to this question myself.</p>
<h1>Turing completeness</h1>
<ul>
<li>As powerful as a Turing machine (TM).</li>
<li>Requires an <strong>infinite memory</strong>. I.e. in practice, no physical device ever can be Turing complete.</li>
<li>Consider a normal <strong>personal computer (PC)</strong>:
<ul>
<li>A specific physical instance is <strong><em>not</em> Turing complete</strong>, as it has finite memory.</li>
<li>However, consider the <strong>concept of a PC</strong> as something where you could add memory on demand. All programs will still work in the same way when you add more memory. For any given input, and any given program, there is a maximum amount of memory such that it should work. (Let's not be pedantic now about the <code>int64</code> memory address limit or things like that. These are technical limits, which could be solved, e.g. by big ints, etc.) Thus, we can say that <strong>the <em>concept of a PC</em> is Turing complete</strong>. This is also called <a href="https://en.wikipedia.org/wiki/Abstract_machine" rel="nofollow noreferrer">an <strong>abstract machine</strong></a>.
So, differentiate between a specific machine or device (PC, RNN, human brain) and a programming language or abstract machine for a programming language. A programming language usually does not have a restriction on the amount of memory it can use, thus programming languages can be Turing complete. See the <a href="https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf" rel="nofollow noreferrer">official C language standard definition</a>, which uses an abstract machine to define the semantics. The main question is, which of those specific classes (PC, RNN, human brain) allows to formulate abstract machine variants, and are those abstract machine variants Turing complete?</li>
</ul>
</li>
<li>Turing completeness is really mostly about the memory concept. Consider any finite state machine/automaton (FSA), and some access to external memory. Depending on the type of memory, you end up in different classes of the <a href="https://en.wikipedia.org/wiki/Chomsky_hierarchy" rel="nofollow noreferrer">Chomsky hierarchy</a>:
<ul>
<li>no memory / finite memory: <a href="https://en.wikipedia.org/wiki/Regular_language" rel="nofollow noreferrer">regular languages</a></li>
<li>single stack: <a href="https://en.wikipedia.org/wiki/Pushdown_automaton" rel="nofollow noreferrer">pushdown automata</a>, <a href="https://en.wikipedia.org/wiki/Context-free_language" rel="nofollow noreferrer">context-free languages</a></li>
<li>two or more stacks: Turing complete, <a href="https://en.wikipedia.org/wiki/Recursively_enumerable_language" rel="nofollow noreferrer">recursively enumerable language</a></li>
</ul>
</li>
</ul>
<h1>Recurrent neural networks (RNN)</h1>
<h2><em>On the computational power of neural nets</em></h2>
<p>An often cited paper is <a href="http://binds.cs.umass.edu/papers/1992_Siegelmann_COLT.pdf" rel="nofollow noreferrer">On the computational power of neural nets, Siegelmann &amp; Sonntag, 1992</a>, which states that RNNs are Turing complete.
This paper assumes that we have rational numbers without limits in the nominator/denominator, i.e. the infinite memory is encoded as rational numbers, or floating point numbers of infinite precision. See also <a href="https://stats.stackexchange.com/questions/220907/meaning-and-proof-of-rnn-can-approximate-any-algorithm">here</a>. Usually we do not model a NN in a way that is operates with rational numbers (without limit). When we restrict ourselves to (R)NNs with finite precision weights and activations, the proof in the paper falls appart, and does not apply anymore. Thus, this paper is not so relevant.</p>
<p>There is a more recent paper, <a href="https://arxiv.org/abs/1805.04908" rel="nofollow noreferrer">On the Practical Computational Power of Finite Precision RNNs for Language Recognition, Weiss et al, 2018</a>, which exactly addresses this.</p>
<h2>Universal approximator</h2>
<p>It is well known that most standard NNs are <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="nofollow noreferrer">universal approximators</a>. This states, that given any function (nonconstant, bounded, and continuous), and given some allowed threshold, you can construct a NN which approximates this function within the allowed threshold.
This is about finite dimensional vector spaces. When we speak about computability, we speak about sequences, thus we have an infinite dimensional vector space. Thus this property is not so relevant.</p>
<h2>Without external memory</h2>
<p>The question is how to define the <em>concept of a standard RNN</em>. In the paper mentioned above, it assumes infinite precision in the activations. But I argue this is not a reasonable concept of a RNN as you never have this. And with this being limited, there is no other way how a concept of a standard RNN can have infinite memory.</p>
<p>Thus, to state it explicitly:
Without external memory, the standard RNN, and also <a href="https://en.wikipedia.org/wiki/Long_short-term_memory" rel="nofollow noreferrer">LSTM</a> is <strong>not Turing complete</strong>.
There is also no straight-forward way how you could define a <em>concept of a RNN</em>, where you could add memory on demand.
The memory of a RNN are the most recent hidden activations. Adding more memory means to change the NN, i.e. adding new neurons, thus adding the internal workings of it. This is like changing the program itself.</p>
<h2>With external memory</h2>
<p>There is the <a href="https://en.wikipedia.org/wiki/Neural_Turing_machine" rel="nofollow noreferrer">Neural Turing machine (NTM)</a> and a few similar models, which have some sort of external memory.
Here it is straight-forward to think about a <em>concept of a NTM</em> where you would add memory on demand.
Thus we can say that <strong>the <em>concept of a NTM</em> is Turing complete</strong>.</p>
<p>There are some details like the type of attentions used in the heads, which needs some adaptation. There is a follow up on the model, the <a href="https://en.wikipedia.org/wiki/Differentiable_neural_computer" rel="nofollow noreferrer">Differentiable neural computer (DNC)</a> which explicitly addresses this, and also has some explicit mechanism to add memory.</p>
<h2>Learning / training</h2>
<p>We spoke mostly about the theoretic computation power.
A very different question is whether the NN can learn such a function. I.e. whether training (gradient search) leads to a NN which has learned a computable function.</p>
<h2>Human brain</h2>
<p>We might interpret the human brain (or any brain) as kind of a complex neural network. We can also ask the question, whether the human brain (model) is Turing complete. See e.g. <a href="https://cs.stackexchange.com/questions/42311/how-is-the-computational-power-of-a-human-brain-comparing-to-a-turing-machine">here</a>. This question is a tricky one. The intuition would say that we are able to perform any kind of computation, thus the human brain is Turing complete. However, the arguments we have outlined here shows that a RNN is not Turing complete. Important is again the memory effect. At some point, the memory capacity of a human brain is not enough to operate on some input. Thus we would need external memory. So, the human brain together with external memory is Turing complete, obviously. But this is maybe not the interesting question (and also assumes that a human brain could be as large as needed to encode any Turing machine program, so there is no upper size of a human brain, which is not really true). More interesting is the question of just the human brain itself, without any external memory. Or basically, how to define the <em>abstract machine</em> or the <em>concept of a human brain</em>? Does this concept allows for infinite memory? Is this straightforward to define?</p>
<p>There is one aspect of the memory in a human brain which is a bit different than in a standard RNN: It can generalize to a high degree, and the addressing mechanism to access certain activations is different. Also, it has some kind of adaptive weights (which however also only can store finite information). So, considering this, it's actually already more similar to a NTM than just a RNN. There are many different kinds of memory in the human brain. Some of it is just as static as a RNN (like the current activations) but other types allow for associative memory like a NTM. And thus the human brain is also similar to a PC, which also has finite memory, whereas the concept of a PC has infinite memory.</p>
<p>So maybe we can say that a concept of a human brain has infinite memory as well, due to the associative memory, and also can be as large as needed to encode any program, and thus <strong>the concept of a human brain is Turing complete</strong>. Maybe this should be called an <strong>abstract human brain</strong> (instance of an <em>abstract machine</em>).</p>
How useful is Turing completeness? are neural nets turing complete?
<p>While reading some papers about the Turing completeness of recurrent neural nets (for example: Turing computability with neural nets, Hava T. Siegelmann and Eduardo D. Sontag, 1991), I got the feeling that the proof which was given there was not really that practical. For example the referenced paper needs a neural network which neuron activity must be of infinity exactness (to reliable represent any rational number). Other proofs need a neural network of infinite size. Clearly, that is not really that practical.</p>

<p>But I started to wonder now if it does make sense at all to ask for Turing completeness. By the strict definition, no computer system nowadays is Turing complete because none of them will be able to simulate the infinite tape.</p>

<p>Interestingly, programming language specification leaves it most often open if they are turing complete or not. It all boils down to the question if they will always be able to allocate more memory and if the function call stack size is infinite. Most specification don't really specify this. Of course all available implementations are limited here, so all practical implementations of programming languages are not Turing complete.</p>

<p>So, what you can say is that all computer systems are just equally powerful as finite state machines and not more.</p>

<p>And that brings me to the question: <strong>How useful is the term Turing complete at all?</strong></p>

<p>And back to neural nets: For any practical implementation of a neural net (including our own brain), they will not be able to represent an infinite number of states, i.e. by the strict definition of Turing completeness, they are not Turing complete. <strong>So does the question if neural nets are Turing complete make sense at all?</strong></p>

<p>The question if they are as powerful as finite state machines was answered already much earlier (1954 by Minsky, the answer of course: yes) and also seems easier to answer. I.e., at least in theory, that was already the proof that they are as powerful as any computer.</p>

<hr>

<p>Some other questions which are more about what I really want to know:</p>

<ul>
<li><p>Is there any theoretical term which can say something more specific about the computational power of a computer? (given its limited memory space)</p></li>
<li><p>How can you compare the computational power of practical implementations of neural nets with computers? (Turing-completeness is not useful as argumented above.)</p></li>
</ul>