0
$\begingroup$

I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$ that is described in the answer of the proof)

So

  1. If $x$ is empty, accept

  2. If $x$ is any non-empty string, reject.

$\endgroup$

1 Answer 1

0
$\begingroup$

You have to be careful when you talk about accepting empty strings. Using the language from the linked question, what you are suggesting would yield $L(M_x)$ = $\{\epsilon\}$ instead of $L(M_x)$ = $\emptyset$.

You can use the same construction for machine $M_x$, but just change the the non-trivial property to "whether this machine accepts on no inputs". It's clearly a non-trivial property since it's not empty (there are machines with empty language), and it's not the set of all Turing Machines (since not all Turing Machines have empty language).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.