retagged by
393 views
1 votes
1 votes

L1 = {<M>| M is a turing machine that accepts all even numbers.}

L2={<M,x>| M is a Turing machine and x is a string and there exists a TM M1 such that x does not belong to L(M) and L(M1)}

 Can someone explain it informally/ intuitivelywithout the concrete proof??

retagged by

1 Answer

0 votes
0 votes
L1 is undeciable, by Rice's theorem.

I don't know about L2.(but I think it is also undecidable).

Related questions