Church’s Thesis, Godelization, Time Complexity of Turing Machine & Halting Problem of TM | Theory of Computation - Computer Science Engineering (CSE) PDF Download

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⁰ � 3³ � 5² � 7¹ � 11²
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₀, x₁, x₂, .......x_n) the associated Godel number, Gn is,
Gn(x₀, x₁, x₂, .......x_n) = 2^x0 3^x1 5^x2 7^x3.........P
where Pⁿ 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 + 3n/2 + 1
Thus the time complexity of TM is O(n²)
    τ(n) = O(n²)

Example 2:
Consider the TM to accept the language, L = {aⁿbⁿ|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²)
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⁴ − 3x² + 2 = 0, and
B is the problem of finding some root of x² − 2 = 0.
Here x² − 2 is a factor of x⁴ − 3x² + 2 = 0.
Thus a root of x² − 2 = 0 will also be a root of x⁴ − 3x² + 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₁, w₁).
It is taken such that M₁ halts on input w₁, iff M accepts w.
The machine M₀ stops when M₁ halts.

Initially, the string w is fed to the TM, M and w₁ is fed to the TM, M₁.
    If M accepts w, then it sends a halt signal to M₁. Then TM, M₁ halts on input w₁.
    If M rejects w, then M₁ does not halt on w₁.
Thus halting of M₁ depends on the acceptance behaviour of M. Acceptance behaviour of a TM is undecidable, halting of M₁ or M₀ is undecidable.