0
$\begingroup$

Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable).

L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)}

For example if I want to represent by diagram a TM $M_1$ that accepts the string 1011 and a TM $M_2$ that doesn't accept the string 1011 (e.g., $M_2$ accepts only the empty string), following the Rice Theorem not-trivial property, I need to use a (1) acceptance by final states or (2) acceptance by halting or (3) I can use both because I know (by theorem) they are equivalent?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.