UNIT-5
UNDECIDABILITY
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable
Problems about TM – Post‘s Correspondence Problem, The Class P and NP
RECURSIVEANDRECURSIVELYENUMERABLELANGUAGES
Recursively Enumerable Language
A language LcΣ*is recursively enumerable if there exist a Turing machine, M that accepts every string,
wϵL and does not accept strings that are not in L.
If the input string is accepted, M halts with the answer ,“YES”.
If the string is not an element of L, then M may not halt and enters into infinite loop.
wєL
M
L
YES
wLoopsForever
The language, L is Turing Acceptable.
Recursive Language
A language is said to be recursive if there exists of Turing machine, M that accepts every
string, wϵL and rejects those strings that are not in L.
If the input is accepted, M halts with the answer ,”YES”
wєL
M
L
YES
wNO
, w L the Turing machine doesn‟t accept the string.
If w L, then M halts with answer, “NO”. This is also called as Turing Decidable language.
PROPERTIESOFRECURSIVEANDRELANGUAGES
1. The union of two recursive language is recursive
2. The language Land its complement L are recursively enumerable, then L is recursive.
3. The complement of a recursive language is recursive.
4. TheUnionoftworecursivelyenumerablelanguagesisrecursivelyenumerable.
5. The intersection of two recursive language is recursive.
6. The intersection of two recursively enumerable language is recursively enumerable
Proofs on the Properties
Property-1
Theunionoftworecursivelyenumerablelanguagesisrecursivelyenumerable.
Proof:
LetL1andL2betworecursivelyenumerablelanguagesacceptedbytheTuring
machinesM1andM2.
If a string wϵL1then M1returns “YES”, accepting the input string: Else loops forever. Similarly
if a stringw ϵL2 then M2returns “YES”, else loops forever.
TheTuringmachineM3thatperformstheunionofL1andL2isgivenas
RE
YES
M1
YES
wєΣ* M3
RE
M2 YES
RE
HeretheoutputofM1andM2are writtenon theinputtape ofM3. The turning
machine,M3returns“YES”,ifatleastoneoftheoutputsofM1andM2is“YES”.TheM3 decides on
L1UL2that halts with the answer, “YES” if wϵL1orwϵL2.ElseM3loops forever if both M1and
M2loop forever.
Hence the union of two recursively enumerable languages is also recursively
enumerable.
Property–2
UNDECIDABILITY
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable
Problems about TM – Post‘s Correspondence Problem, The Class P and NP
RECURSIVEANDRECURSIVELYENUMERABLELANGUAGES
Recursively Enumerable Language
A language LcΣ*is recursively enumerable if there exist a Turing machine, M that accepts every string,
wϵL and does not accept strings that are not in L.
If the input string is accepted, M halts with the answer ,“YES”.
If the string is not an element of L, then M may not halt and enters into infinite loop.
wєL
M
L
YES
wLoopsForever
The language, L is Turing Acceptable.
Recursive Language
A language is said to be recursive if there exists of Turing machine, M that accepts every
string, wϵL and rejects those strings that are not in L.
If the input is accepted, M halts with the answer ,”YES”
wєL
M
L
YES
wNO
, w L the Turing machine doesn‟t accept the string.
If w L, then M halts with answer, “NO”. This is also called as Turing Decidable language.
PROPERTIESOFRECURSIVEANDRELANGUAGES
1. The union of two recursive language is recursive
2. The language Land its complement L are recursively enumerable, then L is recursive.
3. The complement of a recursive language is recursive.
4. TheUnionoftworecursivelyenumerablelanguagesisrecursivelyenumerable.
5. The intersection of two recursive language is recursive.
6. The intersection of two recursively enumerable language is recursively enumerable
Proofs on the Properties
Property-1
Theunionoftworecursivelyenumerablelanguagesisrecursivelyenumerable.
Proof:
LetL1andL2betworecursivelyenumerablelanguagesacceptedbytheTuring
machinesM1andM2.
If a string wϵL1then M1returns “YES”, accepting the input string: Else loops forever. Similarly
if a stringw ϵL2 then M2returns “YES”, else loops forever.
TheTuringmachineM3thatperformstheunionofL1andL2isgivenas
RE
YES
M1
YES
wєΣ* M3
RE
M2 YES
RE
HeretheoutputofM1andM2are writtenon theinputtape ofM3. The turning
machine,M3returns“YES”,ifatleastoneoftheoutputsofM1andM2is“YES”.TheM3 decides on
L1UL2that halts with the answer, “YES” if wϵL1orwϵL2.ElseM3loops forever if both M1and
M2loop forever.
Hence the union of two recursively enumerable languages is also recursively
enumerable.
Property–2
