From reading the page and these comments...<p>A feedforward neural network can be viewed as a &quot;continuous generalization&quot; of a fixed-size circuit, which makes it able to learn any function within the circuit complexity of the network.<p>A deep neural network biases towards circuits that are deeper than they are wide, towards functions composed out of smaller functions.  Since many useful functions are such (and for other theoretical reasons, such as deep networks having &quot;funnels&quot; in their free-energy landscapes), deep learning works well.<p>A recurrent neural network goes from circuits to deterministic finite-state automata.<p>LSTM basically turns the whole thing into a small, fixed-size <i>almost</i> sorta-kinda pushdown automaton, and Neural Turing Machines generalize to a sorta-kinda linear-bounded automaton.<p>This stack approach makes things <i>much</i> more like a real pushdown automaton.  So a feedforward network with a stack should be able to &quot;learn any PDA&quot;, and a recurrent network with an unlimited-size stack should be able to learn more-or-less any Turing machine (though it&#x27;s biased towards Turing machines that &quot;look like&quot; PDAs with funny state transitions).<p>Kinda.  <i>waves hands</i>