Can you apply Rice's Theorem on the following languages? Are they decidable?

$$L_1:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and } M_v \text{ has an even number of states.}\}$$ $$L_2:=\{v\mid v \text{ is the Code of a TM } M_v \text{ and on input }\lambda, \text{ an } a \text{ gets printed during calculation.} \}$$

We can't apply Rice's Theorem to the first language, because the property "has an even number of states" is not dependent on the language, but on the Turing Machine, which can be modified. Therefore, we need to show, that there exists a TM $M$, which halts on every string and $$\forall x \in L: M_v(x)\downarrow \text{ yes}$$ or $$\forall x \notin L: M_v(x)\downarrow \text{ no},$$ which really exists: You could count the number of states in the code-string and accept if it equals $2$ and reject but halt otherwise.

We are able to apply Rice's Theorem on the second language. The property that something depends on the input and output is definately a property of the language, not of the machine which is computing it. The property is not trivial, some languages have this property, the most don't. That's why the language is not decidable.

Are those thoughts in any way correct? Is this too informal or do I left important thinks out? I would be thankful for corrections and hints on how to solve problems in my arguments!

  • $\begingroup$ The second language is not a semantic property: indeed, two machines can have the same language, but one prints $a$ and the other doesn't. So in order to prove undecidability of the second language, you have to give an explicit reduction. $\endgroup$ – Shaull Jan 23 at 10:36

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.