Unit 5
Dr.S.Anitha Elavarasi
Syllabus
Undecidability
• Problems can be classified into
– Decidable categories
– Undecidable categories
(based on whether they can be solved using an algorithm. )
• A decidable problem is one for which a solution can be
found in a finite amount of time, meaning there exists
an algorithm that can always provide a correct answer.
• An undecidable problem is one where no algorithm can
be constructed to solve the problem for all possible
inputs.
Decidable Problems
• Decidability in terms of a Turing machine, a
problem is said to be a Decidable problem if
there exists a corresponding Turing machine
that halts on every input with an answer- yes or
no.
• It is also important to know that these problems
are termed Turing Decidable since a Turing
machine always halts on every input, accepting
or rejecting it.
Semi Decidable Problems
• Semi-decidable problems are those for which a
Turing machine halts on the input accepted by
it but it can either halt or loop forever on the
input which the Turing Machine rejects.
• Such problems are termed as Turing
Recognisable problems.
What are Undecidable Problems?
• The problems for which we can’t construct an
algorithm that can answer the problem correctly
in finite time are termed as Undecidable
Problems.
• These problems may be partially decidable but
they will never be decidable.
• That is there will always be a condition that will
lead the Turing Machine into an infinite loop
without providing an answer at all.
Example of Undecidable
• The halting problem of Turing machine
• The mortality problem
• The mortal matrix problem
• The Post correspondence problem, etc.
Halting problem
Post Corresponds problem
• Post Correspondence Problem is a popular undecidable
problem that was introduced by Emil Leon Post in 1946
• In this problem we have N number of Dominos (tiles).
The aim is to arrange tiles in such order that string made
by Numerators is same as string made by Denominators.
• In simple words, lets assume we have two lists both
containing N words, aim is to find out concatenation of
these words in some sequence such that both lists yield
same result.
Domino’s Form :
Table Form :
Example 1
• Step-1: We will start with tile in which numerator and denominator are starting
with same number, so we can start with ’2’ Lets go with second tile, string
made by numerator- A, string made by denominator is AB.
Numerators : A
Denominators : AB
• Step-2: To match Bs in denominator so we will go with first tile,
Numerators : AB
Denominators : ABCA
• Step-3: To match Cs in denominator so we will go with third tile,
Numerators : ABCA
Denominators : ABCAA
• Step-4: To match As in denominator so we will go with two tile,
Numerators : ABCAA
Denominators : ABCAAAB
• Step-5: To match As in denominator so we will go with four tile,
Numerators : ABCAAABC
Example 2
Example 3 - undeciablity
Binary Encode of TM
• An encoding of TM (or, for that matter, an encoding of any object) Is a
string that fully describes that TM, in the sense that a machine that
emulates M need only read that string to know everything it needs to
know about M.
Binary Encoding TM – Problem 1
Binary Encoding TM – Problem 2
Turing machine to PCB
Turing machine to PCB
Turing machine to PCB
Example
Input String w=01
Example
RULE 1
RULE 2
Example
RULE 3
Example
RULE 4
We must start with first pair
Rule 3 (q10,1q2)
Rule 2
Rule 3 (q21,0q1)
Rule 2
Rule 3 (0q1#, q201#)
Rule 3 (1q20, q310)
Rule4 & rule 2
Home work
Home work
Home work
Find whether there is a solution for the following PCP instance.
d) A= {ba,aba,baa,b} B= {bab,baa,a,aba}
e) A= {10,010,100 } B= {101,100,1,010}
Reference
• Tuningmachine to MPCB
https://www.youtube.com/watch?
v=B3zKSRQtzIg&list=PL6xbXi2C3sePDwyboAcu7l
1UYuUT2SWYd&index=66
