4 ms·

TLDR: Given any Turing Machine you can build a Recurrent Neural Network that does the same thing. You can then apply known facts about Touring machines, e.g. H

TLDR: Given any Turing Machine you can build a Recurrent Neural Network that does the same thing. You can then apply known facts about Touring machines, e.g. Halting Problem, so you can't generally predict when the neural network is gonna get to the final state.

seiji 11y ago
The simplest definition of turing completeness is: a system capable of manipulating symbols with no restrictions on recursive depth. Basically, if you can write "while (true) { doStuff(); }" (or an equivalent TCO version), your system is turing complete. So, all the "deep learning" fads aren't even turing complete (if we don't consider RNNs "deep learning") because they are feedforward/backprop networks of explicitly limited depth. Humans are turing complete, but only for limited time spans. Humans get tied up in a version of the halting problem called "this is dumb let's do something else." It's difficult for humans to execute "find the highest prime number" without other needs derailing the process over time (boredom, bathroom breaks, biological death).
- pygy_ 11y ago
  > "while (true) { doStuff(); }" [...] Humans are turing complete [...] The example I like to give when explaining algorithms and turing completeness to laypeople is "Stir until you get a smooth mix", and by extension, cooking recipes.
  - hobs 11y ago
    After thinking about that for a second, that is my new favorite analogy. Way better than anything I have ever come up with to explain the same thing.
- andreyk 11y ago
  FYI, RNNs are a form of Deep Learning these days (in particular LSTM and GRU RNNs, very popular for language translation and much more for a few years now). There is also research lately into weirder types of neural nets such as 'Neural Turing Machines' (http://arxiv.org/abs/1410.5401 http://arxiv.org/abs/1410.5401).
  - seiji 11y ago
    Sadly, "deep learning" (much like "AI" itself) has become more of a marketing term and less of a technical term these days. If I tell someone I made a deep learning system, it conveys no details other than it's something besides a single linear discriminator. deep learning is in the "Peak of Inflated Expectations" phase of our never ending tech hype cycle. Like most buzzwords, it holds meaning for practitioners, but when marketing dweebs with no knowledge are hired to write endless clickbait about technical terms with no underlying understanding, it dilutes the entire vocabulary ecosystem until even the practitioners can't describe what they do using their own terminology anymore.
    - nbouscal 11y ago
      Given that it's so common to present RNNs as feed-forward nets with a layer for each time step, it doesn't seem at all unreasonable to group them in with deep learning.
    - andreyk 11y ago
      True, it's impossible to argue "deep learning" is not in the midst of a massive hype boom, and it does just generically convey one is using a deep rather than shallow learning approach. But at least the research going on there is still quite exciting, or so it seems to me.
0xdeadbeefbabe 11y ago
My intuition suggests termination analysis is even more difficult with a neural network because you can't open them up and see the code.
- daveguy 11y ago
  Computationally they are the same. Both levels of difficulty are : not possible in general. In special cases they would be algorithmic solutions and the connections in an RNN are just as well defined as statements and function calls in a procedural program.

seiji 11y ago

The simplest definition of turing completeness is: a system capable of manipulating symbols with no restrictions on recursive depth. Basically, if you can write "while (true) { doStuff(); }" (or an equivalent TCO version), your system is turing complete. So, all the "deep learning" fads aren't even turing complete (if we don't consider RNNs "deep learning") because they are feedforward/backprop networks of explicitly limited depth. Humans are turing complete, but only for limited time spans. Humans get tied up in a version of the halting problem called "this is dumb let's do something else." It's difficult for humans to execute "find the highest prime number" without other needs derailing the process over time (boredom, bathroom breaks, biological death).

pygy_ 11y ago
> "while (true) { doStuff(); }" [...] Humans are turing complete [...] The example I like to give when explaining algorithms and turing completeness to laypeople is "Stir until you get a smooth mix", and by extension, cooking recipes.
- hobs 11y ago
  After thinking about that for a second, that is my new favorite analogy. Way better than anything I have ever come up with to explain the same thing.
andreyk 11y ago
FYI, RNNs are a form of Deep Learning these days (in particular LSTM and GRU RNNs, very popular for language translation and much more for a few years now). There is also research lately into weirder types of neural nets such as 'Neural Turing Machines' (http://arxiv.org/abs/1410.5401 http://arxiv.org/abs/1410.5401).
- seiji 11y ago
  Sadly, "deep learning" (much like "AI" itself) has become more of a marketing term and less of a technical term these days. If I tell someone I made a deep learning system, it conveys no details other than it's something besides a single linear discriminator. deep learning is in the "Peak of Inflated Expectations" phase of our never ending tech hype cycle. Like most buzzwords, it holds meaning for practitioners, but when marketing dweebs with no knowledge are hired to write endless clickbait about technical terms with no underlying understanding, it dilutes the entire vocabulary ecosystem until even the practitioners can't describe what they do using their own terminology anymore.
  - nbouscal 11y ago
    Given that it's so common to present RNNs as feed-forward nets with a layer for each time step, it doesn't seem at all unreasonable to group them in with deep learning.
  - andreyk 11y ago
    True, it's impossible to argue "deep learning" is not in the midst of a massive hype boom, and it does just generically convey one is using a deep rather than shallow learning approach. But at least the research going on there is still quite exciting, or so it seems to me.

0xdeadbeefbabe 11y ago

My intuition suggests termination analysis is even more difficult with a neural network because you can't open them up and see the code.

daveguy 11y ago
Computationally they are the same. Both levels of difficulty are : not possible in general. In special cases they would be algorithmic solutions and the connections in an RNN are just as well defined as statements and function calls in a procedural program.