288 views
0 votes
0 votes
If L and Ľ both are recursive enumerable language, then why L is recursive language?

1 Answer

0 votes
0 votes
Let M1 be the recognizer for L

Let M2 be the recognizer for L'

Run M1 and M2 in parallel , x(any arbitrary string) will either belong to M1 or M2.

So , either M1 or M2 will halt and one of them wil accept x

if M1 accept then accept and if M2 accept then reject

Either ways u will eventually halt with a decision and thus  L will be recursive language.........

Related questions

0 votes
0 votes
2 answers
1
Mk Utkarsh asked Nov 26, 2017
2,105 views
If total turing machine is a proper subset of turing machine then why recursive language is not a proper subset of Recursive Enumerable ?
3 votes
3 votes
2 answers
3
Sandeep Verma asked Nov 12, 2017
2,309 views
If a language(L1) is Recursive enumerable (RE) and L2 is Recursive (REC) , then what will be L1 - L2 ? Can we directly use set difference property or do the s...
2 votes
2 votes
1 answer
4
Ajit J asked Dec 25, 2018
2,040 views
What is the complement of a language which is recursively enumerable but not recursive? Is it only non rel or can be both both non rel and recursive?