6
$\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$

1 Answer 1

5
$\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$
6
  • $\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
    Commented Jan 16, 2017 at 19:58
  • $\begingroup$ @Redcoat, good questions! I added another paragraph to my answer; see revised answer (last paragraph). $\endgroup$
    – D.W.
    Commented Jan 16, 2017 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
    Commented Jan 16, 2017 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.
    Commented Jan 17, 2017 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
    Commented Apr 17, 2019 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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