Proving that Rice's theorem does not apply to a property

Question

This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic.

The question is about if Rice theorem applies to certain property. For example for a structural property such as number of states. I would argue that:

• The property is decidable through its definition in encoded form.
• The property is irrelevant to the language, because given the same language we can easily find another TM that does not have this property, ie one with empty states, so the property is not a language property, and hence Rice Theorem does not apply, since by definition, Rice theory only applies if it is a non trivial language property.

To me, this seems to be a good argument, but the question is assign a substantial mark of 10, and I feel like this is not enough for 10 marks, am I missing out some rigorous argument that I need to include to make my explanation crystal clear?

Answer 1

The answer is right but the argument is not sufficient. Try to build a contradicting example as a proof. Describe how to encode each machine into a binary number (can be found in any tcs book). Then choose some random non-trivial property, say the number of states is equal to 4. Show that there is a machine that admit this property and a machine that does not. Finally describe a universal machine deciding this property (which is doable if the encoding is injective/reversible (which is usually the case). Since the example contradicts the theorem, it clearly does not apply here.

The intuitive reason is that you defined a property of a machine (the encoding itself) and not the language accepted by the machine.