# Confused between turing-completeness and universal approximation - are they related?

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!

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).

• 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"? – Spacey Jan 16 '17 at 19:58
• @Redcoat, good questions! I added another paragraph to my answer; see revised answer (last paragraph). – D.W. Jan 16 '17 at 20:03
• 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? – Spacey Jan 16 '17 at 20:08
• @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. – D.W. Jan 17 '17 at 0:41
• 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. – samlaf Apr 17 '19 at 3:39