Lambda Calculus, Computable Function

A computable function (here function doesn't have the meaning of what we have in calculus) is basically nothing but what we usually do in a body of a function or procedure during programming. It is a mathematical term which widely has been used in "Computability Theory".

Let's describe it in this way, you have a function gets some inputs and based on some algorithm it computes required output. The process you do on these inputs to get the result or the applied algorithm can be simply demonstrated by a computable function. It is a formalized mathematical method of describing intuitive notions of algorithms.

Note that if we want to bring exact definition and reasoning of what computable function is or can be derived, we need to go deep in some advanced mathematics and some information on "μ-recursive functions", "Turing Machine", "Register Machine", ... are also required. So for now, we just try to describe things in more descriptive and tangible ways rather than theoretical ways. So again, we just accept by definition that a computable function accepts inputs and after applying a procedure or an algorithm on the given inputs, it calculates the output. Now let us expand our knowledge on computable functions.



Computable Function Example 

• Function which accepts any number n as its argument and returns n*n.
• Function which accepts a natural number n ({1, 2, 3, . . .}) as its argument and returns the nth prime number.
• Any program you've already written can be considered as a computable function.

An Example of NonComputable Function

• The classical example of "Halting Problem". A function that accepts any program and any kind of its inputs as input arguments and returns true if the given program calculates the result or false if it can't calculate the result.
• A function that lists all the way we can calculate 492 from natural numbers.

Other approaches and definitions

• You can also define a Computable Function like F : R-->D which maps elements of R (range) to elements of D (domain) if there exists a program that can simulate the exact behavior of the F. 
• Church–Turing thesis says that computable functions are functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space.
• When you have some inputs and some outputs the function which drives outputs from the inputs is called computable when the inputs to outputs mapping are unique and can be done by a computer.
• Any computable function can be incorporated into a program using while-loops. If you check the examples above all of them have such property. (In fact, this is one of the main features of a bare bone languages, which we will talk about later.)