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