Answers.Body: <p>For an RNN to be trained using teacher-forcing, the recurrence in time must be in the form of output-to-hidden. This is a special case of the more general RNN structure that allows hidden-to-hidden recurrence. The latter can approximate a universal Turing machine with a large enough hidden state, however, the output-to-hidden RNN cannot do so.</p>
  <p>This is fundamentally because the sequence of output does not uniquely specify the future behavior of a Turing machine. The same argument can be made for autoregressive Transformers and time-delay neural networks (TDNN). They are less expressive.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-22T12:46:55.483Z
Answers.LastActivityDate: 2024-01-22T12:46:55.483Z
Answers.UserDisplayName: Memming
Body: <p><a href="https://ai.stackexchange.com/questions/33814/is-the-capability-of-rnn-more-than-the-capability-of-mlp">RNN has the same capability as a universal Turing machine</a>. But I am confused whether RNN holds the same capabilities if we use teacher forcing.</p>
  <p>Consider the following excerpts from paragraphs taken from the section titled &quot;Teacher Forcing and Networks with Output Recurrence&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>.</p>
  <blockquote>
  <p><strong>The network with recurrent connections only from the output at one time step to the hidden units at the next time step is strictly less
  powerful because it lacks hidden-to-hidden recurrent connections. For
  example, it cannot simulate a universal Turing machine</strong>. Because this
  network lacks hidden-to-hidden recurrence, it requires that the output
  units capture all the information about the past that the network will
  use to predict the future....... Models that have recurrent
  connections from their outputs leading back into the model <strong>may be</strong>
  trained with teacher forcing.</p>
  </blockquote>
  <p>The quoted portion says that the RNN in which recurrent connections only exist from the output at one time step to the hidden units at the next time step are less powerful and are not as capable as a universal Turing machine. And those neural networks can be trained with teacher forcing. Even though they are not trained using teacher forcing, they are not as capable as the universal Turing machines. But, I want to get clarity on the relation between the capability of RNN trained using teacher forcing and the capability of universal Turing machine.</p>
  <p>Is it true that if an RNN is trained with teacher forcing then it cannot simulate a universal Turing machine?</p>
  
Tags: <comparison><recurrent-neural-networks><theory-of-computation><teacher-forcing><turing-completeness>
Title: Can teacher forcing in RNN ensure Turing completeness?
UserDisplayName: hanugm
ThreadText: # Can teacher forcing in RNN ensure Turing completeness?
  
  (Asked by: username_0 on 2021-12-20)
  
  [RNN has the same capability as a universal Turing machine](https://ai.stackexchange.com/questions/33814/is-the-capability-of-rnn-more-than-the-capability-of-mlp). But I am confused whether RNN holds the same capabilities if we use teacher forcing.
  
  Consider the following excerpts from paragraphs taken from the section titled "Teacher Forcing and Networks with Output Recurrence" 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*.
  
  > **The network with recurrent connections only from the output at one time step to the hidden units at the next time step is strictly less
  > powerful because it lacks hidden-to-hidden recurrent connections. For
  > example, it cannot simulate a universal Turing machine**. Because this
  > network lacks hidden-to-hidden recurrence, it requires that the output
  > units capture all the information about the past that the network will
  > use to predict the future....... Models that have recurrent
  > connections from their outputs leading back into the model **may be**
  > trained with teacher forcing.
  
  The quoted portion says that the RNN in which recurrent connections only exist from the output at one time step to the hidden units at the next time step are less powerful and are not as capable as a universal Turing machine. And those neural networks can be trained with teacher forcing. Even though they are not trained using teacher forcing, they are not as capable as the universal Turing machines. But, I want to get clarity on the relation between the capability of RNN trained using teacher forcing and the capability of universal Turing machine.
  
  Is it true that if an RNN is trained with teacher forcing then it cannot simulate a universal Turing machine?
  
  **Tags:** comparison, recurrent-neural-networks, theory-of-computation, teacher-forcing, turing-completeness
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-01-22. Score: 0
  
  For an RNN to be trained using teacher-forcing, the recurrence in time must be in the form of output-to-hidden. This is a special case of the more general RNN structure that allows hidden-to-hidden recurrence. The latter can approximate a universal Turing machine with a large enough hidden state, however, the output-to-hidden RNN cannot do so.
  
  This is fundamentally because the sequence of output does not uniquely specify the future behavior of a Turing machine. The same argument can be made for autoregressive Transformers and time-delay neural networks (TDNN). They are less expressive.
  
  
  ---
  
  