455 views

2 Answers

Best answer
3 votes
3 votes

$L = \left \{ <M> \right \}$ Where $M$ is some TM encoding.

Now, Let's analyze the given Two conditions for $M$ one by one.

1. $M$ is a $TM$ that Halts on All the inputs :  From this condition/point, We have gotten to know that $M$ is a Halting TM, And since the language accepted by any Halting TM(HTM) is Recursive language, We can say that $L(M)$ is Recursive. 

2. $L(M)$ = $L'$ for some Undecidable language $L'$ : Undecidable language means "Not recursive language". So, From this 2nd condition we have that $L(M)$ is some NOT Recursive language (i.e. Undecidable language)

So, Now, From the First condition we have "$L(M)$ is Recursive" and from the second condition we have "L(M) is NOT recursive"... So, Both are contradictory, Hence we can say that there is NO such $M$ possible. Hence, $L$ is Empty language. Hence, $L$ is Regular language and Hence $L$ is Recursive and decidable (Every recursive language is Decidable).

selected by
0 votes
0 votes
note 1:Turing machine means recusive enumerable language for which there is three possibilities accept reject and looping hence due to looping we say Rec enum languages are not deciadable with respect to membership

note2:now TOTAL TUring m/c means recursive language for which there is only two possibilities either accept or reject so Recusrive language are deciadable ....

L1 is halting problem of turing machine  refer the note 1 it is undecidable but question specifically says halts on every string  nd m is a encoded turing machine i.e just a string so it is decidable so L(m)=recursive

L2 IS

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
3
jugnu1337 asked Sep 3, 2023
329 views
FIND the no of 2 state dfa with the designated initial state possible over {a,b,c} which accept empty language is equal to