Body: <p>Consider the following excerpt paragraph taken from the section titled &quot;Recurrent Neural Networks&quot; of the <a href="https://www.deeplearningbook.org/contents/rnn.html" rel="nofollow noreferrer">chapter 10: Sequence Modeling: Recurrent and Recursive Nets</a> of the textbook named <a href="https://www.deeplearningbook.org/" rel="nofollow noreferrer">Deep Learning</a> by <em>Ian Goodfellow et al</em> on the computational graph of some computations.</p>
  <blockquote>
  <p>The recurrent neural network of ..... is universal in the sense that
  <strong>any function computable by a Turing machine can be computed by such a
  recurrent network of a ﬁnite size</strong>. The output can be read from the RNN
  after a number of time steps that is asymptotically linear in the
  number of time steps used by the Turing machine and asymptotically
  linear in the length of the input. The functions computable by a
  Turing machine are discrete, so these results regard exact
  implementation of the function, <strong>not approximations</strong>. The RNN, when used
  as a Turing machine, takes a binary sequence as input, and its outputs
  must be discretized to provide a binary output. It is possible to
  compute all functions in this setting using a single speciﬁc RNN of
  ﬁnite size. The “input” of the Turing machine is a speciﬁcation of the
  function to be computed, so the same network that simulates this
  Turing machine is suﬃcient for all problems. The theoretical RNN used
  for the proof can simulate an unbounded stack by representing its
  activations and weights with rational numbers of unbounded precision.</p>
  </blockquote>
  <p>This paragraph clearly explains that RNN is capable of computing any computable function <em>exactly</em> and is the same as the Turing machine in terms of capability.</p>
  <p>Afaik, MLP is capable of <em>approximating</em> any continuous, bounded function.</p>
  <p>So, it seems to me that RNN is more powerful in terms of the capability of computing functions than MLP. RNN can learn any function that MLP can learn and RNN can learn more than that can be learned by any MLP in general.</p>
  <p>Am I correct? Or is there any issue in my interpretation or do more details need to be considered?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-18T15:20:51.407Z
Comments.Text: The way MLP works usually work with sequences restricts to the fixed length sequence, since feature vectors from multiple timesteps are concatenated to single vector of big dimension. RNN can handle arbitrary long sequence on the other hand.
Comments.UserDisplayName: spiridon_the_sun_rotator
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-19T04:23:54.627Z
Comments.Text: @spiridon_the_sun_rotator But, but I think it is possible to assume an MLP with infinite input length.
Comments.UserDisplayName: hanugm
Tags: <comparison><recurrent-neural-networks><multilayer-perceptrons><universal-approximation-theorems><turing-completeness>
Title: Is the capability of RNN more than the capability of MLP?
UserDisplayName: hanugm
ThreadText: # Is the capability of RNN more than the capability of MLP?
  
  (Asked by: username_0 on 2021-12-18)
  
  Consider the following excerpt paragraph taken from the section titled "Recurrent Neural Networks" of the [chapter 10: Sequence Modeling: Recurrent and Recursive Nets](https://www.deeplearningbook.org/contents/rnn.html) of the textbook named [Deep Learning](https://www.deeplearningbook.org/) by *Ian Goodfellow et al* on the computational graph of some computations.
  
  > The recurrent neural network of ..... is universal in the sense that
  > **any function computable by a Turing machine can be computed by such a
  > recurrent network of a ﬁnite size**. The output can be read from the RNN
  > after a number of time steps that is asymptotically linear in the
  > number of time steps used by the Turing machine and asymptotically
  > linear in the length of the input. The functions computable by a
  > Turing machine are discrete, so these results regard exact
  > implementation of the function, **not approximations**. The RNN, when used
  > as a Turing machine, takes a binary sequence as input, and its outputs
  > must be discretized to provide a binary output. It is possible to
  > compute all functions in this setting using a single speciﬁc RNN of
  > ﬁnite size. The “input” of the Turing machine is a speciﬁcation of the
  > function to be computed, so the same network that simulates this
  > Turing machine is suﬃcient for all problems. The theoretical RNN used
  > for the proof can simulate an unbounded stack by representing its
  > activations and weights with rational numbers of unbounded precision.
  
  This paragraph clearly explains that RNN is capable of computing any computable function *exactly* and is the same as the Turing machine in terms of capability.
  
  Afaik, MLP is capable of *approximating* any continuous, bounded function.
  
  So, it seems to me that RNN is more powerful in terms of the capability of computing functions than MLP. RNN can learn any function that MLP can learn and RNN can learn more than that can be learned by any MLP in general.
  
  Am I correct? Or is there any issue in my interpretation or do more details need to be considered?
  
  **Tags:** comparison, recurrent-neural-networks, multilayer-perceptrons, universal-approximation-theorems, turing-completeness
  > **Comments:**
  > **username_1**: The way MLP works usually work with sequences restricts to the fixed length sequence, since feature vectors from multiple timesteps are concatenated to single vector of big dimension. RNN can handle arbitrary long sequence on the other hand.  
  > **username_0**: @spiridon_the_sun_rotator But, but I think it is possible to assume an MLP with infinite input length.  
  
  ---
  
  ## 0 answers
  
  