Does there exist an equivalent arithmetic circuit for each computable function?
I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe the statement to be false.
What has made me curious is that I've read some theorems stating that a protocol (cryptograhy protocol theory) can compute any computable function, but then requires that the function should be specified as an arithmetic circuit.
Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\mathbb{F}$ of the form:
$$f(x_1,...,x_n)=\sum\limits_{i_1+...+i_n\le d}\alpha _{i_1,...,i_n}\cdot x_1^{i_1}x_2^{i_2}...x_n^{i_n}$$
where $\alpha _{i_1,...,i_n}\in\mathbb{F}$ are the coefficients of the multivariate polynomial.
There are many computable functions that cannot be expressed as a polynomial, e.g. take $f:\mathbb{Q}\rightarrow\mathbb{Q}$ which is $1$ at $x=0$ and zero everywhere else. Since $f$ is non constant with an infinite number of zeros, it cannot be written as a univariate polynomial.
Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate polynomial $p(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n) = p(x_1,\dots,x_n)$ for all $x_1,\dots,x_n$, where arithmetic is done modulo two (i.e., over the field $\mathbb{F}_2=\{0,1\}$). Now every multivariate polynomial can be computed by a an arithmetic circuit, so $f$ can be computed by an arithmetic circuit.
In some sense the restrictions to fixed-length inputs is unavoidable, as any circuit inherently has a fixed number of inputs and a fixed number of outputs. So once you decide to focus on boolean functions, then the statement you saw in the crypto literature is justified: any boolean function that can be computed by a circuit, can be computed by an arithmetic circuit. And, any computable boolean function can be computed by arithmetic circuits, where we understand "computed" to mean that there is a family of arithmetic circuits, one per input length (the non-uniform model; this is unavoidable if you want to compute using circuits, as any one circuit can only have a fixed input length).
