1

The Pitfall of Algorithmic Computing: Undecidability

A decision problem is one that can be answered with a “yes” or a “no”. The underlying process
involved in the solution of a decision problem is known as the decision–making process.

The process of decision making cannot go on forever and has to terminate after a finite number of
step with a categorical answer, “Yes” or “No”. This aspect of the decision making process intuitively
links it to the concept of algorithm, which stop after a finite number of steps with some answer.
Therefore, if a machine has to make a decision, then the corresponding process should be
implementable on the machine in the form of an algorithm. If this is the case, then the problem is
decidable; otherwise, it is undecidable. A decidable problem in its “yes” instance is normally
associated with some sort of solution as well. Therefore, certain authors refer to the concept of
decidability in the form of solvability as well.

Language recognition is also a decision problem where in the problem to be answered is, “Given a
string w and a language L, does w ∈L?”

If w ∈ L, then the answer to the decision problem is “yes”; otherwise, “no” .In an automated
environment, this task has to be accomplished by some machine, say M. The machine M can be the
instance of any language recognition machine such as finite automaton, pushdown automation, linear
bound automation, Turing machine or some other machine .Thus it is expected that for every instance
of string w over ∑* ,the machine M will stop and say either “yes” or “no” .The machine do the job as
instructed ; hence it is mandatory that the set of instructions given to the machine be unambiguous
and deterministic so that it is clearly understood and executed in a mechanical manner without any
dilemma.

Alan Turing and Alanzo Church ,in their famous “Church –Turing Thesis” ,claimed that “Any
algorithmic set of instruction can be implemented on a Turing machine” .We go by their claim and say
that a problem is decidable or solvable if we have a Turing machine for it.

RECURSIVE AND NON –RECURSIVE LANGUAGES

A language L is recursive if we have the corresponding Turing machines that halts in final state to say
“Yes” if w ∈ L and halts in the non final state to say “no” if w ∉ L. For a given character set ∑,
∑*denotes the universe of the language .Every language L over ∑ is some subset of ∑*. The
complement of a language L, =∑*-L is a set of all the string that are not in L.

1. If the structure of a language L is such that the corresponding machine that will halt in a final state
for every string w∈ L and in a non–final state for every string w ∉ L ,then L is known to be a recursive
language .

2. If the structure of a language L is such that the corresponding machine will halt in a final state for
every string w ∈ L, but for every string w ∉ L, halting of the machine cannot be guaranteed, then L is
known as a recursively enumerable language.

3. If the structure of a language L is such that the recognition machine cannot be designed for it, then
the L is neither recursive nor recursive enumerable.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 1 | P a g e

 1

A machine designed for the language L , on being given a string w over ∑*

1. Halts to answer in “yes” if the language L is recursive or recursively enumerable, if w ∈ L; and

2. Halts to answer in “no” if the language L is recursive, if w ∉ L . It may not halt to say “no” if
the language is recursively enumerable.

Halting of the machine cannot be guaranteed if the language is neither recursive nor recursively
enumerable, independent of whether w belong to L or not.

Recognition and Acceptance

A recursively enumerable language is said to be accepted by a Turing machine and is
referred to as a Turing acceptable language. A recursive language is said to be recognized
by a Turing machine and is referred to as Turing decidable Language .Now let us talk
about certain aspects related to recursive and recursively enumerable languages.

Theorem 8.1 If a language L is recursive, Then its complement is

also recursive.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 2 | P a g e

 1

Let M be the Turing machine for language L .Since L is recursive ,for every string w ∈ ∑* the
machine M will halt in the final state if w ∈ L and in non final state if w ∉ L. Thus, M will halt
eventually.

In addition ,if w ∈ L then w ∉ and if w ∉L then w ∈ .Hence ,we can say that M halts in the
final state if w ∉ and in the non final state if w ∈ .Thus ,M halt in the both cases of but
convey the reverse message .If the output message are inverted then the result will correspond to
. Figure 8.2 shows the machine M’ for .M’ is derived from M with output messages inverted.

For w ∈ , M’ halts to say yes. For w ∉ , M’ halts to say no. Since we have been able to create
machine M’ for that halts in both cases , c is a recursive language.

Theorem 8.2 If two languages L1 and L2 are recursive, then their union L1 U L2 is also recursive.

Proof :- Let M1 be the Turing machine for language L 1 and M2 be the Turing machine for language L 2.
Since L1 is recursive, for every string w ∈ ∑* , M1 will halt in the final state to say “yes” if w ∈ L1 and
will halt in the non final state to say “no” ,if w ∉ L1. Similarly, for every string w ∈ ∑* , M2 will halt in
the final state to say “yes” if w∈ L2 and will halt in the non final state to say “no” if w ∉ L2.

Now , w ∈ L1UL2 if w ∈ L1 , w ∈ L2 ,or both .The design and working of machine M’ for L 1UL2 is as
follows ;

1. The string w is fed to M1 and M2 and machine M1 is started.

2. If w ∈ L1 ,then M1 halts in the final state to say “yes”, thereby stopping M’ to say “yes”.
3.If w ∉L1 , then M1 halts in a non final state to say “no” .This no signal from M1 starts M2 ,and
w is checked for belongingness to L2 on M2 .
4.If w ∈ L2 , M2 halts in the final state to say “yes” ,thereby stopping M’ to say “yes” .
5.If w ∉ L2 ,M2 halts in the non final state to say “no” ,thereby stopping M’ to say “no”.

M’ halts to say “yes” if w belongs to either L1 or L2 and halts to say “no” if w belongs to neither L1 nor
L2 . Since there is a machine M’ for L 1UL2 that halts in both cases to appropriately say “yes” or “no” for
any given string w ,L1UL2 is a recursive language .Figure 8.3 shows the design of M’.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 3 | P a g e

 1

Theorem 8.3 If two languages L1 and L2 are recursive, then their intersection L1∩L2 is also
recursive.

Proof : Let M1 be the Turing Machine for the language L1 and M2 be the Turing machine for language L2
,Since L1 is recursive ,for every string w ∈ ∑* ,M1 will halt in the final state to say “yes” if w∈L1 and
will halt in the non final state to say “no” if w ∉ L1 .Similarly ,for every string w ∈∑* ,M2 will halt in
the final state to say “yes” if w ∈ L2 and will halt in the non final state to say “no” if w ∉ L2.

Now, w ∈ L1 ∩ L2 if w ∈ L1 and w ∈ L2 as well .The design and working to Turing machine M’ for L 1 ∩
L2 is as follows:

1. The string w is fed to both M1 and M2 and M1 is started.

2. If w ∉ L1, then M1halts in a non-final state to say “no”, thereby stopping M’ to say “no”.
3. If w∈L1, then M1 halts in the final state to say “yes” .This “yes” signal from the machine M1
starts the machine M2 and “w” is checked for belongingness to L2 on M2.
4. If w ∈ L2, M2 halts in the final state to say “yes”, thereby stopping the M’ to say “yes”.
5. If w ∉ L2, M2 halts in the non–final state to say “no”, thereby stopping the M’ to say “no”.

The machine M’ halts to say “yes” if w belongs to L 1 as well as L2 and halts to say “no” if w does
not belongs to both L1 and L2 simultaneously .Since there is a machine M’ for L1 ∩ L2 that halts in
both case to appropriately say “yes” or “no” for any given string, L 1∩L2 is recursive language.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 4 | P a g e

 1

Figure 8.4 machines for L1 ∩ L2

Theorem 8.4 If a language L and its complement are both recursively enumerable, then L is a
recursive language.

Proof : Let M1 be the Turing machine for L .Since L is a recursively enumerable language ,for every
string w ∈ L , M1 halts in a final state to say “yes” .However ,for the string w∉ L ,stopping of M1
cannot be guaranteed and it may continue to run non-stop forever.

Let M2 be the Turing machine for .Since is a recursively enumerable language, for every string w
∈ M2 halts in a final state to say “yes” .However ,for the string w ∉ ,stopping of M2 cannot be
guaranteed .

Now for a string w ,if w ∈ L ,then M1 stops in the final state to say “yes” ,and if w ∈ ,then M2 stops
in the final states to say “yes” .Thus for every string w ∈∑* ,either M1 or M2 will stop. Stopping of M 1
indicates w ∈ L and stopping of M2 indicates w ∈ , that is, w ∉ L .Thus, the recognition machine M
for the language L can be designed as follows:

M consists of both M 1 and M2. M halts when either of the machines M 1 or M2 halts. If M1 halts , then
M halts in “yes” state to indicate w ∈ L and if M2 halts ,then M halts in “no” state to indicate w ∉ L .
Now , we have a recognition machine that halts in both cases of L .Hence L is a recursive language .

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 5 | P a g e

 1

Figure 8.5 shows the structure of machine M.

Theorem 8.5 Let L1 ,L2 ,L3 ,…..LK be the set of recursively enumerable languages over ∑ such
that they form a partition set over ∑* .Prove that each of the languages L 1,L2 ,L3 ,….Lk is
recursive .

Proof: The languages L1,L2,L3 ,…………….LK form a partition set over ∑* meaning that

1. All these languages are mutually exclusive and have no string in common; that is, if a string
w belongs to the language Li , then it cannot belong to any other language LJ when i≠j.
2. Given a string w belonging to ∑*, it is bound to belong to one of the language L1,L2,L3 ,…….LK
Let M1,M2,M3,…………MK be the Turing machines for the languages L 1,L2,L3,……LK respectively .
Now, for a given string w, when fed to all these Turing Machine, exactly one Turing Machine
will halt, whereas the other Turing machines will continue to move .This is the Turing machine
to whose language the input string belongs.
Now it is possible to design a machine M that recognize the language L i . The string w to be
checked for belongingness to L i is fed to all Turing machine in parallel. Now ,if w belongs to L i ,
then the Turing Machine Mi stops and other continue to move .If w does not belongs to L i ,
then some other Turing machine stops .M stops when any of these Turing machine stop. If M i
stops then M stops to say “yes”, and if any other Turing machine stops then M stops to say
“no” . Thus, M is a machine to recognize language L i that stops in both cases .Thus L i is a
recursive language .Taking different values of i ranging from 1 to k it can be proved that all
languages L1,L2,L3 ,……………LK are recursive .The structure of machine M is shown in figure 8.6

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 6 | P a g e

 1

Theorem 8.6 If two languages L 1 and L2 are recursive enumerable, then their union L 1UL2 is
also recursive enumerable.

Proof: Let M1 be the Turing Machine for language L 1 and M2 be the Turing machine for language L 2.
Since L1 is recursive enumerable, for every string w ∈ L1 M1 will halt in the final state to say “yes” .
Similarly, for every string w ∈ L2, M2 will halt in the final state to say “yes”.

Now, w ∈ L1 U L2 if w ∈ L1 ,w ∈ L2 ,or both .The machine M’ for L 1 U L2 can be designed as follows .The
string w is initially fed to both M 1 and M2 and both are started .The machine M’ halts when either M 1
or M2 halts .If w ∈ L1 then M1 halts in the final state to say “yes”, thereby stopping M’ to say “yes”. If
w ∈ L2 ,M2 halts in the final state to say “yes” ,thereby stopping M’ to say “yes” .Thus, the machine M’
will come to halt to say “yes” if w belongs to L1 or L2 ,that is ,if w ∈ L1 U L2.

If w ∉ L1 and w ∉ L2, then neither M1 nor M2 may halt and M’ may continue non-stop. Thus M’
behaves as follows for the language L1 U L2:

1. It halts to say “yes” if w ∈ L1 U L2 .

2. It may continue non-stop if w ∉ L1 and w ∉ L2, that is, when w ∉ L1 U L2.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 7 | P a g e

 1

Thus ,L1 U L2 is a recursively enumerable language .Figure 8.7 shows the design of M’.

Fig 8.7 Machine for L1 U L2

Theorem 8.7 If two languages L1 and L2 are recursive enumerable, then their intersection L 1∩
L2 is also recursive enumerable.

Proof:- Let M1 be the Turing machine for language L 1 and M2 be the Turing machine for language L 2 .
Since L1 is recursive enumerable, for every string w ∈ L1, M1 will halt in the final state to say “yes”.
Similarly, for every string w ∈ L2, M2 will halt in the final state to say “yes”.

Now, w∈ L1 ∩ L2 if w ∈ L1 and w ∈ L2 or both .The machine M’ for L1 ∩ L2 can be designed as follows.

The string w is fed to both M1 and M2 in parallel and M1 is started .If w ∈ L1 ,then M1 halts in the final
state to say “yes” and sends a starts signal to M 2 to get it started .If w ∈ L2 ,M2 halts in the final state
to say “yes”, thereby stopping M’ to say “yes” .Thus ,M’ will come to a halt to say “yes” if w belongs to
both L1 and L2 that is ,if w ∈ L1 ∩ L2 .

If w ∉ L1 or w∉ L2 , then either M1 or M2 may not halt and M’ may continue non–stop .Thus M’
behaves as follows for the language L1 ∩ L2 .

1. It halts to say yes if w ∈ L1∩L2 .

2. It may continue non–stop if w ∉ L1 or w ∉ L2, that is, when w ∉ L1 ∩ L2 .

Thus, L1 ∩ L2 is a recursively enumerable language .Figure 8.8 shows the design of M’.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 8 | P a g e

 1

Fig 8.8 Machine for L1 ∩ L2

CHURCH TURING THESIS

In the theory of computation, the Church-Turing thesis, named after Alonzo Church and Alan
Turing, talks about mechanical calculation devices and a kind of calculations they can perform. The
statement of the thesis, in Turing’s own words, is

“Every function which would naturally be regarded as computable can be computed by a Turing
machine.”

Due to the vagueness of the concept of a function that can be regarded as computable, it is not
possible to prove or disprove this thesis formally. It is for this reason that some people call it a
conjecture.

Some more definitions of the Church-Turing thesis are as follows:

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

2. For every computable 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 Turing machine is the same as that which can
be decided by any mechanical computing machine.

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

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 9 | P a g e

 1

The last statement talks about the concepts of algorithms. Although there is no formal definition
for the concept of algorithms, we can talk about certain properties related to the algorithms
that are generally agreed upon.

1. An algorithm is a finite set of precise instructions, which are to be followed in a mechanical

manner, using a finite number of symbols.

2. The instructions in an algorithm can be executed in a mechanical manner; therefore its

execution does not need human intelligence except that needed to understand and execute
the instructions.

3. An algorithm can, in principle, be carried out by a human being with only a paper and
pencil.

4. An algorithm always produces the result after a finite number of steps.

Church’s thesis was proposed prior to the design of Turing machine. What Church actually said
was that any machine that could do a certain list of operations could perform all the algorithms
that can be conceived .These operations involved recursive and computable functions related to
the work of Godel and Hilbert. The Turing machine was able to meet the requirements proposed
by Church and was conceived as the model machine for the implementation of all conceivable
algorithms. The idea behind the design of the Turing Machine was based on human limitation of
the calculation process.

Turing said that when a human performs a computation using paper and pencil, it involves
making certain marks on the paper initially, and on looking at these marks he/she makes new
marks on the paper, which are used to write further new marks. The process of writing the new
marks is based on some rules that are to be followed, by humans, in a mechanical manner.
Keeping these aspects in view, Turing proposed his computing machine, which scans the old
marks and writes new ones on the basis of old marks by following some definition rules. Thus,
the Turing machine was proposed by Church as a machine that could perform any function
defined by humans and whose calculations could be performed using a well defined algorithm.

The relationship between the design of a Turing machine and the concept of algorithm is
circular, with each one defining the other. The Turing machine is supposed to solve what
humans can solve using a set of rigid rules.

As described earlier, the Church-Turing thesis is a conjecture which cannot be proved or

disproved. The reason for this is that the concepts such as defined by humans and whose
calculation can be performed using an algorithm are not part of any branch of mathematics
and cannot be defined formally.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 10 | P a g e

 1

Despite being a conjecture, in formal terms, the Church-Turing thesis is generally accepted
because of the following reasons

1. All the modifications proposed to the original Turing machine in the form of multitape,
multitrack and nondeterministic versions are reducible to the original Turing machine.

2. Since the introduction of the Turing machine, no one has proposed any type of computation
that ought to be included in the category of algorithmic process but cannot be performed on a
Turing machine.

Automata Theory and Formal Languages CS-404 Munish .Khanna @CSE.HCST.SGI 11 | P a g e