About Turing Machines, this article is a must.

http://plato.stanford.edu/entries/turing-machine/

Simply say, A Truing Machine is composed of 5 elements.

- Initial State s0
- Final State f0
- A
**finite**set of state S - A
**finite**set of input symbols I - A series of functions S x I –> S x I x {L, R, 0}

Of course there are others such as tape, read|write head etc.

In this article, it discusses a method to store number by Turing machine, which is different from normal binary system used by current computers. That is, 0 represented by one 1. 1 by two 1s. 2 by three 1s. … …

Using this representation, it gives a Turing machine to define f(n)=n+1.

Further, it gives a Turing machine of f(m,n)=m+n.

Turing machines can be encoded as sequences of 0|1. Further its arguments and it can be set as input of a UTM(Universal Turing Machine) to simulate its behavior. UTM can be thought of as a programmable computer. And Turing machines can be thought of as a program.

Further, UTM can also be encoded as 0|1 sequences and set as input to itself to simulate its behavior.

The number of Turing machine is countable. And computable functions can be represented by a Turing machine.

The number of functions over Natural numbers is uncountable.(https://proofwiki.org/wiki/Natural_Number_Functions_are_Uncountable)

So there exists functions which can not be represented by a Turing machine.

Let us take a look at the way to prove Functions over Natural Number is uncountable(**F**: NxN).

Firstly, for each n, let us construct the function Fn(x): N—>n, Fn(x) is indefinite and bijectioin to N. So the set of Fn(x) is countable.

Secondly, assuming F is countable, so there exists a bijection M: N—>Qn(x)，Qn(x) belong to **F**. Now let us construct another a bijection P: N—>Qn(x)+1,

for each m belongiing to N, P(m)=Qn(m)+1

Qn(m)+1 is a Natural number,

so P is a member of **F**.

On the other side, P is different from each of Qn(x), so **F** is uncountable.

The above method to prove **F** is uncountable is similar to the way of proving the sequence of 0|1 is uncountable by Cantor.

Let us see what is the common way.

Assuming the set **S** is countable, then construct an element **E** from some or all of the set’s elements. On one side, E is not identical to any of the set’s element. On the other side, from the set’s definition, E also belong to S. Contradiction happens here. So S is not countable.