Siegelmann and Sontag (1991)

(http://www.dlsi.ua.es/~mlf/nnafmc/papers/siegelmann91turing.pdf) show that a single-input single-output DTRNN can simulate any TM; in particular, they show that the UTM may always be encoded in a DTRNN with far less than 100 000 state units. Their architecture is a simple first-order DTRNN (a ``neural Moore machine''):

$$x_i[t]=g_\sigma\left(\sum_{j=1}^{n_X} W^{xx}_{ij} x_j[t-1] + W^{xu}_{i} u[t] + W_i^x\right)$$

$$y[t]=x_1[t]$$

where the $x_i[t]$ are rational numbers, the $u[t]$ are either 0 or 1 and $g_\sigma(x)$ is $0$ if $x<0$, $1$ if $x>1$ and $x$ otherwise.

The input tape is the sequence $u[1]u[2]\ldots$; the output tape is the sequence $y[1]y[2]\ldots$.

The proof by Siegelmann and Sontag (1991) stands on the following findings:

• A TM may always be simulated by a pushdown automaton with three unary stacks (counters) [indeed, only two are needed (Hopcroft and Ullman, 1979, 172)].
• A unary stack may be encoded as a fractional number (in binary): $q_s=0.1111=15/16$ represents four items. Popping an item is the same as taking $q_s'=\sigma(2q_s-1)$; pushing an item is the same as taking $q_s'=\sigma(1/2+q_s/2)$.
• All stack operations and all state transitions triggered by states of the control unit and the symbols at the top of stacks may be computed in at most two time steps of the DTRNN.