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


Siegelmann (1995):

This author has shown that the above first-order DTRNN using real instead of rational state values have super-Turing computational power. The computational power of DTRNN is similar to that of nonuniform Turing machines, that is, nonrealizable TM that receive in their tape, in addition to the input $w$, another string $W(\vert w\vert)$ called ``advice'' (a function only of the length of $w$) to assist in the computation5.9.

In particular, the computational class P/Poly refers to those nonuniform Turing machines in which both the length of the advice and the computational time are polynomially (not exponentially) long (relative to the length of $w$). DTRNN compute the super-Turing class P/Poly in polynomial time too.



Debian User 2002-01-21