Proof of universality in the circuit model

Question

I'm starting to study Turing machines, the Church-Turing conjecture and the circuit model. In particular, I'm interested in the proofs of universality that one can find in this context. So far, I have only found the universality proof of the circuit model for boolean functions (i.e., the gates AND, OR and NOT can be used to compute any boolean function). However, our experience with digital computers indicates that they can approximate really well more things than only boolean functions.

My question is: are there more proofs of universality in the context of the circuit model? For example, to approximate continuous funcitons. I have tried to find something about this particular case but I didn't find any proof nor any reference where approximation of continuous functions with boolean functions is discussed. And it is something that puzzles me because, in the context of machine learning, feed-forward neural networks are universal approximators of continuous functions, but we compute the feed-forward neural networks models in digital computers. All the possible references are wellcome!

Answer 1

I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting problem). This directly implies that TMs can't approximate any classical continuous function arbitrarily well. E.g. you could create the number $$\xi = \sum_{i = 0}^\infty 2^{-i} h_i$$ where $h_i$ is $1$ if the $i$-th TM halts and $0$ if it doesn't for some mapping of $\mathbb{N}$ to the TMs. It's clear that $\xi \in \mathbb{R}$ and that you could work with the function $f(x) = \xi x^2 +\xi^2$ in analysis and differentiate it without a problem, but it's not computable, you can't approximate it's value arbitrarily well. One interesting field of study it computable analysis which deals with deals with a special kind of analysis where only functions and numbers are considered that are computable (arbitrarily closely approximatable by a TM).

Now let us take a look at circuits. It's true that you can for a given table of inputs and outputs of a Boolean function construct a circuit that computes that table. The problem is that the table is sometimes not computable in the first place. E.g. you could say that the circuit $C_n$ taken a binary representation of a TM up to length $n$ as input an outputs $0$ if it doesn't halt on the emtpy tape and $1$ if it halts. Now all circuits in the sequence $C_1, C_2, ...$ do exist in the sense that they are in the set of all possible circuits, but you can not build them, because of the halting problem. (It is very similar to $\xi$ it exists but you can not compute it). This also applies to your continuous functions. E.g. lets look at the function $f(n) = \xi$ (which is a normal real continues function). You could now define that $C_{n,k}$ is a circuit that takes $k$ as a binary number ($k < 2^i$) as input and computes $f(n)$ up to a precision of $2^{-k}$ that is $k$ places after the comma in binary. Now there are circuits $C_{1,1} C_{2,1}, ...$ that exist, because the mappings are all binary and if you had the Boolean tables for any particular $n,k$ you could build a circuit, but you can't compute the Boolean tables..., I hope you get a feel for the problem with computability and that there exists things, which you can define and use, but not construct. To answer your question, yes you can approximate continues functions with circuit sequences arbitrarily well, but that does not mean that there is an algorithm to find such circuits...

Anyhow I would recommend you to look into computable analysis. It seems to be what you are searching for.