[Solved]: Mathematical function vs Computer program

Problem Detail: 

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration.

Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets.

Then relation $R \subseteq A_1\times A_2\times A_3 \times A_n$ .

Here $X$ represents cross product betwen two sets.

If we consider first $k$ sets as input domain and next $n-k$ sets as output range.

Then $R$ is an $k$-ary function that returns $n-k$ multiple outputs. $0 \le k \le n$

As we know function is a well-behaved relation. i.e.., A relation can assign same input to any number of outputs.

In the case of functions (well-beahaved relations) one input at most maps to one output.

My doubt is whether

1. Any program written in any program language ultimately a mathematical relation.

2. Any program written in any program language ultimately a mathematical function.

3. Some programs written in programming languages cannot be a mathematical relation.

4. Some programs written in programming languages cannot be a mathematical function.

We know that 2. $\implies$ 1. and 3. $\implies$ 4.

Which of the four arguments above are true for all set of programs in all programming languages?

I am arguing with my colleague that 1.,2. are true independent of programming language and program.

But his argument is that procedural languages like c, c++, pascal etc.., doesn't obey 2. but in case of functional programming languages like Haskell it's true.

So, is functional programming is syntactical extension of mathematical functions or conceptual extension?

Asked By : hanugm

Answered By : jmite

So, the notion of mathematical function is broader than that of a computable function i.e. one you can write in a programming language. There are some mathematical functions which can't be written as programs, such as the function from binary encodings of Turing Machines to booleans representing whether that machine halts on every input.

A Turing machine can be thought of as a function in one of two ways. In case 1, it's a function from its alphabet $\Sigma^*$ to the set ${\top, \bot}$ of boolean values, where the value for an input string is either true if the machine accepts, or false if it does not. This is also what corresponds to a decision problem in formal language theory. The second, more complex way, is where we see a Turing machine as a function from $\Sigma^*$ to $\Sigma^*$, where the value for an input string is whatever value is on the tape at the time of termination.

Note that all other types of Turing machines, such as non-deterministic, multi-tape, etc. can be converted into a deterministic one. (Unless you get something really weird that can do infinite computation in finite time). Also, you can encode most mathematical data in strings, but things get complicated for things such as real numbers or certain infinite sets.

The lambda calculus interpretation is more straight-forward. The lambda calculus is a term rewriting system, where everything is a function. A lambda calculus expression can usually be taken to a normal (irreducible) form through some sequence of $\beta$ and $\eta$ reductions. (Beta-reduction is basically just substituting values for arguments, eta is just writing $\lambda x . f x$ as $f$).

So, every lambda-calculus expression $f$ can be viewed as a function from lambda-calculus expressions to lambda-calculus normal forms, where the value of $f$ with argument $a$ (some other expression) is the normal form of $f a$. Again, most things, like integers, strings, etc, can be encoded in the lambda-calculus, but some things, such as real numbers, are more tricky.

Now's where things get fun. This is all assuming a lambda-calculus or Turing-machine model. What these are very bad at modelling is IO, or some interaction with the outside world.

The Haskell approach to this is to view these as pure functions with some "world" argument, which gets destroyed every time it's updated (a new world state is created).

Likewise, for something like interactive programs, you can stretch our definitions and model the pixels shown on the screen, the files written to disk, the audio waves played, etc. as bits which are part of the program's output.

For example, consider a Python program which prints the current date and time $n$ times for some argument $n$. At first glance, this isn't a function, since you can give it the same $n$ and get a different result. However, if you view the state of the world, namely the current date and time, as an argument to the program, then it always does give the same result for the same input, it's just that input is physically impossible to reproduce because we don't control the passage of time. (You could fudge the computer clock if you wanted, but you can apply the same principal to physical sensors and such).

So, let's look at your four specific questions.

1. Yes (see 2 below).
2. Yes, by expressing that program either as a Turing Machine or $\lambda$-calculus expression.
3. No, see 4.
4. No, assuming that you model programs with IO as taking the entire state of the world as input and outputting a new state of the world as output. Otherwise, yes.

You have to be careful, because some languages, such as Prolog, let you write something that's closer to a relation than a function. But at the end of the day, if you massage the notation enough you get something that is a function.

Best Answer from StackOverflow

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