5
$\begingroup$

I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem".

The context here is deep neural nets: So, consider two types of networks: a recurrent neural net, (RNN), and a feedforward net, say a pure convolutional neural net (CNN).

I understand that the RNN is turing complete. I also know that a CNN is a universal approximator, but is NOT turing complete.

What I am trying to understand is the link between universal approximation, and turing-completeness: Is there a link? Why is a CNN a universal approximator but NOT turing complete? Does a machine being turing-complete automatically make it a universal approximator? Trying to uncouple the two concepts.

Thanks!

$\endgroup$
4
$\begingroup$

A CNN can approximate a function on a fixed number of input variables, say $n$ of them. The set of functions on $n$ input variables isn't "Turing-complete". For instance, a boolean function $f:\{0,1\}^n \to \{0,1\}$ is always computable, as it can be computed by a program that just hardcodes the truth-table of $f$; and the set of such functions is not "Turing-complete".

Complication: CNN's actually approximate continuous functions $f:\mathbb{R}^n \to \mathbb{R}$... but a similar point remains (at least if the input is bounded).

Turing-completeness isn't really connected to universal approximation. For one thing: Turing-completeness talks about languages, which are subsets of $\{0,1\}^*$ and thus refers to discrete entities. Universal approximations talks about functions $f:\mathbb{R}^n \to \mathbb{R}$, and thus refers to continuous entities.

To qualify for "universal approximation", it's enough to be able to approximate all functions of $n$ variables (for each function, there exists a neural network that approximates it), so it talks about functions on inputs of bounded length. Turing-completeness requires the ability to compute all computable functions, which is a set of functions that has no fixed upper limit on the number of variables, i.e., it is a set of functions on inputs of unbounded length. Universal approximation could thus, in some sense, be considered "weaker" than Turing-completeness (though strictly speaking they are incomparable; neither implies the other).

$\endgroup$
  • $\begingroup$ Hmm, thanks for the answer, although I am still confused somewhat: Let me phrase a different way: How is it that a non-turing-complete machine can also be a universal approximator? Does that mean that universal-approximation is a "weaker" criteria of machines that "turing-completeness"? $\endgroup$ – Spacey Jan 16 '17 at 19:58
  • $\begingroup$ @Redcoat, good questions! I added another paragraph to my answer; see revised answer (last paragraph). $\endgroup$ – D.W. Jan 16 '17 at 20:03
  • $\begingroup$ Thanks DW! It is getting clearer - however in my mind, there does seem to be a link: For example, it seems to me then, that one cannot have a turing-machine that is NOT a universal approximator simultaneously, right? In that sense, being turing-complete, would also mean that you are a universal approximator. Would you agree with this? $\endgroup$ – Spacey Jan 16 '17 at 20:08
  • $\begingroup$ @Redcoat, I don't agree, because Turing-complete talks about functions on booleans, while universal-approximator talks about functions on real numbers. At this point I suspect maybe what would be most useful would be to familiarize yourself with the precise, mathematical definition of each of those two concepts. $\endgroup$ – D.W. Jan 17 '17 at 0:41
  • $\begingroup$ Would the BSS machine (from what I understand, real-valued TM) be a way to link these concepts? It seems that being BSS-complete implies both Turing-complete and Universal Approximator. $\endgroup$ – samlaf Apr 17 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.