[Solved]: Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function?

Problem Detail: 

I hope that this question is clear, and not off-topic:

I have been reading about neural networks (in the AI sense), and the textbook said that an artificial neural network can always be described by a single mathematical function (rather than by an "algorithm" in a register-machine, which is the standard way I intuitively look at an AI neural network).

So this made me think: is it possible for any arbitrary algorithm, meaning an arbitrary Turing machine, to be simulated by a mathematical function? (I do not mean a function as used in programming languages).

By simulated in this case I mean that given any arbitrary input in the algorithm, that function produces the same output as the algorithm.

Asked By : Programmer2134

Answered By : Ariel

Suppose $M$ is a Turing machine which halts for all inputs $x\in\Sigma^*$, then we can define the corresponding function $f_M$ in the following way:

$$ f_M(x) = \begin{cases} 1, & \text{M accepts x} \\ 0, & \text{otherwise} \end{cases} \quad $$

$f_M(x)$ is a legitimate mathematical function from $\Sigma^*$ to $\left\{0,1\right\}$, it does not care about concepts such as "machine" or "algorithm" or any implementation you have in mind. Obviously the function $f_M$ was tailored for the machine $M$, but this does not make it illegitimate in any way.

You could ask whether i can describe the output of $M$ using a simple function? Perhaps using only the four basic arithmetical operations (we can treat the input strings as numbers represented in binary). The term you should look up in this regard is expressibility, what functions can your model express? For example, when talking about neural nets, the more neurons we use, the bigger our expressive power gets (we can implement more functions).

Note that the converse is not true, not every function can be described by a Turing machine (look up the arithmetical hierarchy, a famous example is the halting problem, but we got a whole hierarchy of even "harder" functions).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62328