A function is computable if it can be computed by a Turing machine.
A Turing machine is a very simple machine, but, logically speaking, has all the power of any digital computer. It may be described as follows: A Turing machine processes an infinite tape. This tape is divided into squares, any square of which may contain a symbol from a finite alphabet, with the restriction that there can be only finitely many non-blank squares on the tape. At any time, the Turing machine has a read/write head positioned at some square on the tape. Furthermore, at any time, the Turing machine is in any one of a finite number of internal states. The Turing machine is further specified by a set of instructions of the following form:
Nowadays it is natural to think of the set of instructions as a program for the Turing machine.
There are several conventions commonly used in Turing machines (and several slightly different, though of course logically equivalent, definitions of them). We adopt the convention that numbers are represented in unary notation, i.e., that the non-negative integer n is represented by a string of n+1 successive1s. Furthermore, if we want to compute a function f(n1,n2, ... ,nk), we assume that initially the tape consists of n1, n2, ... , nk, properly encoded, with each separated from the previous one by a single blank, and with the tape head initially poised over the left-most bit of the first argument, and the state of the Turing machine some initial specified value. We say that the Turing machine has computed m = f(n1,n2,,,,nk) if, when the machine halts, the tape consists of n1, n2, ... , nk, m, properly encoded, and separated by single blanks, and the read/write head back at the left-most bit of the first argument.
For example, suppose we wish to create a Turing machine to compute the
_<1>1 1 1 _ 1 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _which encodes 3 and 4 respectively, in unary notation. (Here the position of the read/write head is marked.) Then the Turing machine should halt with its tape reading
_<1>1 1 1 _ 1 1 1 1 1 _ 1 1 1 1 1 1 1 1 1 1 1 1 1 _ _ _ _ _which encodes 3, 4, and 12 in unary notation.
If you want to know more about these machines. you can mail me.