next up previous contents index
Next: Super-Turing capabilities of DTRNN Up: Turing computability with DTRNN Previous: Turing computability with DTRNN   Contents   Index

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''):

\begin{displaymath}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)\end{displaymath}


\begin{displaymath}y[t]=x_1[t]\end{displaymath}

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:


next up previous contents index
Next: Super-Turing capabilities of DTRNN Up: Turing computability with DTRNN Previous: Turing computability with DTRNN   Contents   Index
Debian User 2002-01-21