Questions: Rice's Theorem and Non-Trivial Turing Machine Properties

Question 1

Which of the following questions about a Turing machine M is covered by Rice's theorem and therefore undecidable?

• A. Does M have more than 500 states in its state diagram?
• B. Does M's transition function contain more than 1000 entries?
• C. Does M accept the string '0110'?
• D. Does M have exactly three tape symbols?

Answer: (C)

Rice's theorem covers non-trivial properties of the *language* recognized by a Turing machine — semantic questions about behavior. 'Does M accept the string 0110?' is a question about what M computes: some machines accept it, others don't, so it's non-trivial. This is undecidable. The other three options are syntactic properties of the machine's *description* — you can answer them by inspecting the state diagram or transition table directly without running the machine. These are decidable.

Question 2

A programmer claims they have written a tool that can perfectly detect all malware by analyzing program code. What does Rice's theorem say about this claim?

• A. The claim is possible as long as the tool only checks static properties of the code, not runtime behavior
• B. The claim is impossible — 'behaves maliciously' is a non-trivial property of the language a program computes, so no algorithm can decide it for all programs
• C. The claim is possible if the tool uses heuristics rather than a deterministic algorithm
• D. Rice's theorem only applies to Turing machines, not to real programming languages

Answer: (B)

'Does this program behave maliciously?' is a property of the computation — it holds for some programs (those that delete files, exfiltrate data, etc.) and not others, making it non-trivial. By Rice's theorem, no algorithm can decide this property for all programs. Any real malware detector must therefore either produce false positives, false negatives, or give up on some inputs. This is a direct real-world consequence of Rice's theorem — not a theoretical curiosity.

Question 3

Rice's theorem implies that any question about a Turing machine is undecidable.

• T. True
• F. False

Answer: False

Rice's theorem applies only to non-trivial properties of the *language* recognized by a Turing machine — semantic questions about what the machine computes. Syntactic properties of the machine's description are decidable: counting states, examining transition functions, checking the machine's structure. 'Does this TM have more than 100 states?' is decidable by inspection. The theorem's scope is specifically behavioral questions about languages, not structural questions about machines.

Question 4

The question 'Does this Turing machine recognize the empty language?' is undecidable by Rice's theorem.

• T. True
• F. False

Answer: True

This is a non-trivial property of languages: some Turing machines recognize the empty language (they accept nothing) and others do not. Since it holds for some RE languages and not all, it is non-trivial, and Rice's theorem applies — no algorithm can decide it for all Turing machines. In fact, this specific property (the emptiness problem for RE languages) was one of the early known undecidable problems, and Rice's theorem later explained why it and dozens of similar properties must all be undecidable.

Question 5

What is the difference between a 'property of the machine' and a 'property of the language,' and why does the distinction determine whether Rice's theorem applies?

Model answer: A property of the machine is a fact about the machine's description or structure — number of states, size of the transition function, specific symbols used. These can be checked by reading the machine's code without running it. A property of the language is a fact about what the machine computes — which strings it accepts, whether it accepts any strings, whether its language is infinite. These require understanding the machine's behavior on all possible inputs, which in general cannot be done by an algorithm. Rice's theorem applies only to the second category.

The dividing line is: can you answer the question by inspecting the code, or do you need to predict behavior? Inspecting code is always decidable; predicting behavior on all inputs runs into the halting problem and undecidability. This distinction has direct software engineering consequences: static analysis (inspecting code) is decidable but imprecise; dynamic analysis (observing behavior) is more informative but can never be complete. Perfect program verification is impossible by Rice's theorem.