Are Neural Nets Turing Equivalent?
Guo-Zheng Sun
sun at umiacs.UMD.EDU
Thu Sep 20 20:39:54 EDT 1990
In addition to Peter Cariani's description, I would like to make a short
comment:
Is any finite state machine with a potential unlimited number of states
(e.g. a recurrent neural net state machine with potential unbounded
precision) equivalent to a Turing machine?
The answer is certainly "NO", because the classical definition of Turing
machine requires both an infinite tape and a set of processing rules with
finite description. Therefore, whether we say one neural net is equivalent
to a finite automaton with potential unlimited number of states or it is
equivalnet to a Turing machine depends on if we can find a set of transition
rules with finite description ( or as Touretzky's words "the wiring schedule
with finite description).
Guo-Zheng Sun
More information about the Connectionists
mailing list