Next: Grammatical inference with DTRNN
Up: Super-Turing capabilities of DTRNN
Previous: Super-Turing capabilities of DTRNN
  Contents
  Index
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 , another string called ``advice''
(a function only of the length of ) 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 ).
DTRNN compute the super-Turing class P/Poly in polynomial time
too.
Debian User
2002-01-21