The document Church’s Thesis, Godelization, Time Complexity of Turing Machine and Halting Problem of TM Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Part V. Church’s Thesis**

**8 Church’s Thesis**

It is also called Church- Turing thesis.

Church’s thesis states that

A function is said to be computable if it can be computed by a Turing machine.

This thesis talks about mechanical computation devices and the kind of computations they can perform.

Some more definitions of this thesis are given below:

1. Any mechanical computation can be performed by a Turing machine.

2. For every computational problem, there is a corresponding Turing machine.

3. Turing machines can be used to model any mechanical computer.

4. The set of languages that can be decided by a TM is the same as that which can be decided by any mechanical computing machine.

5. If there is no TM that decides problem P, there is no algorithm that can solve problem P.

**Part VI. Godelization**

**9 Godelization**

Godelization is an encoding technique which encodes a string as a number. This is called as Godel numbering.

Godel numbering is based on the concept that every positive integer can be factored into a unique set of prime factors.

For example,

6 = 2 x 3

8 = 2 x 2 x 2

9 = 3 x 3

10 = 2 x 5

20 = 2 x 2 x 5

30 = 2 x 3 x 5

50 = 2 x 5 x 5

100 = 2 x 2 x 5 x 5

5,71,725 = 3 x 3 x 3 x 5 x 5 x 7 x 11 x 11

Also, it is possible to assign a serial number to each prime number, as

1 to 2

2 to 3

3 to 5

4 to 7

5 to 11, and so on.

Now the number,

5,71,725 = 3 x 3 x 3 x 5 x 5 x 7 x 11 x 11 = 2^{0} � 3^{3} � 5^{2 }� 7^{1} � 11^{2}

can be represented in the form of a sequence (0, 3, 2, 1, 2).

In terms of Godel numbering, we say that the Godel number associated with the sequence (0, 3, 2, 1, 2) is 5,71,725.

Thus the formal definition of Godel numbering is,

For any finite sequence (x_{0}, x_{1}, x_{2}, .......x_{n}) the associated Godel number, Gn is,

Gn(x_{0}, x_{1}, x_{2}, .......x_{n}) = 2^{x0} 3^{x1} 5^{x2} 7^{x3}.........P

where P^{n} is the n^{th} prime number.

The importance of Godel numbering lies in the fact that each Godel number encodes a unique sequence and a sequence encodes a unique Godel number.

This allows us to represent different configurations of a multi parameter dependent object in the form of a unique number.

A TM at any instant, can exist in different configurations, with each configuration being defined by the current state and position of the head. The position of the head can be defined by a cell number. It is possible to number each state and each cell, and to encode every configuration of a TM in the form of a Godel number. Also, it is possible to define every

transition function of a TM in the form of a Godel number.

**Part VII. Time Complexity of Turing Machine****10 Time Complexity of Turing Machine**

A Turing machine takes a string w, it gives the output in the form yes or no. Here it is possible to exactly measure the

number of moves made by the head of the TM during the processing of the string.

Although the number of moves made by the TM to process the string depend on the specific string, it is possible to

make an estimate of the maximum possible number of moves that TM will make to accept or reject a string of length of n.

Time complexity of a Turing machine, M is written as,

τ_{M}(n)

where τ is the time complexity, n is a natural number.

Time complexity of a TM is the maximum number of moves made by the head to accept or reject a string of length n in

the worst case scenario.

**Example 1:**

Consider the TM to accept the language, L = {wwR|w ∈ (a, b)^{+}}

Find the time complexity of the TM.

Let the string is of length n.

Here the TM works as follows:

It checks the first symbol of the input string, converts it to #, and travels the whole of the string and reaches the # just

following the string. It turns back and matches the last symbol of the string with the first one. If the match occurs, this last

symbol is replaced with a #. Next the head travels back to the second symbol of the input string.

Here the number of moves required is 2n + 1.

On reaching the second symbol, it finds its corresponding match.

Here the number of moves required is 2n - 3.

When al lthe pairs are successfully matched, TM just makes one move and halts.

The worst case is one in which the input string is valid and the TM has to match all the corresponding pairs. Also, with every match, number of moves required to match the next symbol decreases. the process stops when all the symbols are successfully matched and no move is required. Now the TM halts.

Total number of moves made by the TM is,

(2n+1) + (2n-3) + (2n-7) + ...... + 1

= ( (2n+1) + 1) /2 x (n/2 +1)

= (n+1) x (n/2 +1)

=n^{2}/2 + 3n/2 + 1

Thus the time complexity of TM is O(n^{2})

τ(n) = O(n^{2})

**Example 2:**

Consider the TM to accept the language, L = {a^{n}b^{n}|n ≥ 1}

Find the time complexity of the TM.

Here head replaces leftmost 0 by x and leftmost 1 by y. Then head reaches back to the second symbol. Here 2n moves are needed.

Thus at most 2n moves are needed to match a 0 with a 1.

For matching all 0s with 1s, this process is to be repeated n/2 times.

Then the total number of moves needed is around 2n x n/2. That is O(n^{2})

Time complexity of this TM is,

τ(n) = O(n2)

**Part VIII. Halting Problem of TM**

Here we use a process called reduction.

Let A is the problem of finding some root of x^{4} − 3x^{2} + 2 = 0, and

B is the problem of finding some root of x^{2 }− 2 = 0.

Here x^{2} − 2 is a factor of x^{4} − 3x^{2} + 2 = 0.

Thus a root of x^{2} − 2 = 0 will also be a root of x^{4} − 3x^{2} + 2 = 0.

Then we can say that A is reducible to B.

Thus a problem A is reducible to problem B if a solution to problem B can be used to solve problem A.

Then if A is reducible to B and B is decidable, then A is decidable.

If A is reducible to B and A is undecidable, then B is undecidable.

**11 Halting Problem of TM**

This problem states that halting problem of a Turing machine is undecidable.

Proof

To show this, we reduce problem of halting to a problem of acceptance. Consider the following TM,

Here we take an instance (M, w) and construct another instance (M_{1}, w_{1}).

It is taken such that M_{1} halts on input w_{1}, iff M accepts w.

The machine M_{0} stops when M_{1} halts.

Initially, the string w is fed to the TM, M and w_{1} is fed to the TM, M_{1}.

If M accepts w, then it sends a halt signal to M_{1}. Then TM, M_{1} halts on input w_{1}.

If M rejects w, then M_{1} does not halt on w_{1}.

Thus halting of M_{1} depends on the acceptance behaviour of M. Acceptance behaviour of a TM is undecidable, halting of M_{1} or M_{0} is undecidable.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|44 docs|39 tests