About Turing Machines, this article is a must.



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

  1. Initial State                                  s0
  2. Final State                                   f0
  3. A finite set of state                      S
  4. A finite set of input symbols        I 
  5. 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.