Chapter Two
Un decidability
Introduction to Un decidability
In the theory of computation, we often come across such
problems that are answered either 'yes' or 'no'.
The class of problems which can be answered as 'yes' are called
solvable or decidable. Otherwise, the class of problems is said
to be unsolvable or un decidable.
Un decidability of Universal Languages:
The universal language Lu is a recursively enumerable language
and we have to prove that it is un decidable (non-recursive).
Theorem: Lu is RE but not recursive.
If some language or problem is not Turing-
decidable then we call it un decidable.
Intuitively, this means that for this problem
there is no algorithm that is correct and
terminates on all inputs.
To establish the un decidability of the halting
problem, we will consider a situation where
we run a Turing machine/algorithm on its own
encoding/source code.
Con..
Consider that language Lu is recursively enumerable
language. We will assume that L u is recursive.
Then the complement of L u that is L`u is also
recursive. However, if we have a TM M to accept
L`u then we can construct a TM L d. But Ld the
diagonalization language is not RE.
Thus our assumption that Lu is recursive is wrong
(not RE means not recursive). Hence we can say
that Lu is RE but not recursive.
Un decidable Problem about Turing
Machine
In this section, we will discuss all the un
decidable problems regarding Turing machine.
The reduction is used to prove whether given
language is desirable or not. In this section, we
will understand the concept of reduction first
and then we will see an important theorem in
this regard.
Reduction
Reduction is a technique in which if a problem P1 is reduced
to a problem P2 then any solution of P2 solves P1.
In general, if we have an algorithm to convert an instance of
a problem P1 to an instance of a problem P2 that have the
same answer then it is called as P1 reduced P2.
Hence if P1 is not recursive then P2 is also not recursive.
Similarly, if P1 is not recursively enumerable then P2 also is
not recursively enumerable.
Theorem: if P1 is reduced to P2 then
1. If P1 is un decidable, then P2 is also un decidable.
2. If P1 is non-RE, then P2 is also non-RE.
Proof
1. Consider an instance w of P1. Then construct an algorithm such that the
algorithm takes instance w as input and converts it into another instance x of
P2. Then apply that algorithm to check whether x is in P2. If the algorithm
answer 'yes' then that means x is in P2, similarly we can also say that w is in
P1. Since we have obtained P2 after reduction of P1. Similarly if algorithm
answer 'no' then x is not in P2, that also means w is not in P1. This proves that
if P1 is un decidable, then P1 is also un decidable.
2. We assume that P1 is non-RE but P2 is RE. Now construct an algorithm to
reduce P1 to P2, but by this algorithm, P2 will be recognized. That means there
will be a Turing machine that says 'yes' if the input is P2 but may or may not
halt for the input which is not in P2. As we know that one can convert an
instance of w in P1 to an instance x in P2. Then apply a TM to check whether x
is in P2. If x is accepted that also means w is accepted. This procedure
describes a TM whose language is P1 if w is in P1 then x is also in P2 and if w
is not in P1 then x is also not in P2. This proves that if P1 is non-RE then P2 is
also non-RE.
Chomsky Hierarchy
• Chomsky Hierarchy represents the class of
languages that are accepted by the different
machine.
• The category of language in Chomsky's
Hierarchy is as given below:
1. Type 0 known as Unrestricted Grammar.
2. Type 1 known as Context Sensitive Grammar.
3. Type 2 known as Context Free Grammar.
4. Type 3 Regular Grammar.
This is a hierarchy. Therefore every language
of type 3 is also of type 2, 1 and 0.
Similarly, every language of type 2 is also of
type 1 and type 0, etc.
Type 0 Grammar:
Type 0 grammar is known as Unrestricted
grammar. There is no restriction on the
grammar rules of these types of languages.
These languages can be efficiently modelled
by Turing machines.
For example:
bAa → aa
S→s
Type 1 Grammar
Type 1 grammar is known as Context Sensitive Grammar. The context
sensitive grammar is used to represent context sensitive language. The
context sensitive grammar follows the following rules:
The context sensitive grammar may have more than one symbol on the left
hand side of their production rules.
The number of symbols on the left-hand side must not exceed the number
of symbols on the right-hand side.
The rule of the form A → ε is not allowed unless A is a start symbol. It
does not occur on the right-hand side of any rule.
The Type 1 grammar should be Type 0. In type 1, Production is in the
form of V → T Where the count of symbol in V is less than or equal to T.
For example:
S → AT
T → xy
A→a
Type 2 Grammar
Type 2 Grammar is known as Context Free Grammar.
Context free languages are the languages which can be
represented by the context free grammar (CFG). Type 2
should be type 1.
The production rule is of the form A → α
Where A is any single non-terminal and is any combination
of terminals and non-terminals.
For example:
A → aBb
A→b
B→a
Type 3 Grammar
Type 3 Grammar is known as Regular Grammar. Regular
languages are those languages which can be described
using regular expressions. These languages can be
modelled by NFA or DFA.
Type 3 is most restricted form of grammar. The Type 3
grammar should be Type 2 and Type 1. Type 3 should be
in the form of
V → T*V / T*
For example:
A → xy
Turing Recognizable, Turing Decidable and
Turing Enumerable
A Turing Machine can end up in one of three
possibilities
1. Accept and halt by ending up in
2. Reject and halt by ending up in
3. Run forever
Turing Recognizable
The language recognized by a Turing Machine
is the set of strings that the machine accepts.
A language is Turing recognizable if it is
recognized by some Turing Machine. Thus, if
a string belongs to a language that is Turing
recognizable, there exists some Turing
Machine which will accept that string.
However, strings that do not belong to the
language may run forever.
Turing Decidable
A Turing Machine is a decider if it halts on every
input.
A language is Turing decidable if it is recognized by
a Turing Machine decider. Thus, in addition to the
Turing Machine accepting all strings that belong to
the language, it should reject all strings that do not
belong to the language. The machine halts on every
input.
It is easy to see that every Turing Decidable
language is Turing Recognizable.
Turing Enumerable
A Turing Machine (with an additional output tape) is
an enumerator for a language if when started on an empty
input, it writes all strings that belong to the language on the
output tape. For the sake of clarity, each string is separated by
a distinct symbol.
A TM enumerator ensures two things
Only strings that belong to the language appear on the output
tape
If a string belongs to the language, it will be written on the
output tape after some finite amount of time.
While enumerating, the strings can appear multiple times
or/and out-of-order.
A language is Turing enumerable if some Turing Machine
enumerates it.
Summery
A language L is decidable if both L and L’ are
Turing-recognizable.
The halting problem is Turing-recognizable
but un decidable.
The complement language H’ is an example of
a language that is not even Turing-
recognizable.
