Questions: Rice's Theorem: Deciding Properties of Programs

Question 1

A software company wants to build a tool to automatically verify whether any submitted program correctly implements a given algorithm specification. What does Rice's theorem say about this goal?

• A. This is a syntactic property (checking code structure against a spec), so such tools are fully decidable with sufficient engineering
• B. This is a semantic property — 'does this program compute function f?' — and since it is non-trivial, Rice's theorem applies and it is undecidable for arbitrary programs
• C. Rice's theorem does not apply here because the tool only checks finite programs submitted by users, not arbitrary Turing machines
• D. This is decidable because modern compilers can trace all execution paths through any finite program

Answer: (B)

Correctness checking asks whether a program's input-output behavior matches a specification — a semantic property (depends on what is computed, not how the code is textually written). It is non-trivial: some programs implement the spec, others do not. Both conditions hold, so Rice's theorem applies and the problem is undecidable in general. Options C and D are common escape-hatch attempts: Rice's theorem applies to all Turing-equivalent models, and 'tracing execution paths' hits the halting problem for programs with loops.

Question 2

Which of the following properties of Turing machines is decidable?

• A. This machine halts on every possible input
• B. This machine computes the squaring function (outputs n² on input n for all n)
• C. This machine's description contains exactly 47 states
• D. This machine ever outputs the string '42' on any input

Answer: (C)

Option C is syntactic — it depends only on the machine's description (count the states, compare to 47) and can be decided by reading the description without any simulation. It does not depend on what the machine computes. The other three are semantic: they make claims about the machine's behavior over all inputs or over all outputs. Rice's theorem applies to all three, making them undecidable. The key diagnostic question is: could you decide this property by inspecting the machine description alone, without running it?

Question 3

Rice's theorem implies that most questions about program behavior are undecidable, which means static analysis tools like type checkers and linters are fundamentally useless.

• T. True
• F. False

Answer: False

Rice's theorem rules out general algorithms that decide a property for ALL programs. Static analysis tools are useful precisely because they work on decidable approximations: they analyze syntactic patterns, restrict to bounded inputs, over-approximate behaviors (accepting some false positives or negatives), or restrict to specific program structures like type-annotated code. Rice's theorem explains why no tool can be simultaneously sound (no false negatives), complete (no false positives), and fully general — not why no useful tool can exist.

Question 4

The property 'Does this Turing machine accept any input at all?' is a semantic, non-trivial property to which Rice's theorem applies, making it undecidable.

• T. True
• F. False

Answer: True

Whether a machine accepts any input is a claim about its computed language — a semantic property (depends on behavior, not description). It is non-trivial: the machine that immediately halts and rejects every input has an empty language; the machine that accepts any input containing the letter 'a' does not. Since both conditions for Rice's theorem hold, the emptiness problem for Turing machines is undecidable. (This contrasts with finite automata, where emptiness is decidable because FSAs cannot simulate arbitrary computation.)

Question 5

Explain the distinction between semantic and syntactic properties of Turing machines, and why correctly classifying a property is the critical first step in applying Rice's theorem.

Model answer: A syntactic property depends only on the machine's description — its states, transitions, and tape alphabet — and can be checked without running the machine. Example: 'this machine has more than 100 states' is decidable by reading the description. A semantic property depends on the function computed — the machine's input-output behavior over all possible inputs. Example: 'this machine halts on all inputs' requires knowing what happens over infinitely many runs. Rice's theorem applies only to semantic properties that are non-trivial. Misclassifying a syntactic property as semantic (or vice versa) leads to wrong undecidability conclusions.

This classification skill is the core practical application of Rice's theorem. Before invoking it, ask: does this property depend on what the machine *does* (semantic) or on how it is *built* (syntactic)? If semantic and non-trivial (some machines have it, some don't), Rice's theorem immediately gives undecidability with no reduction needed. Many questions in software verification — correctness, specification conformance, absence of bugs — are semantic, which is why Rice's theorem sets the fundamental ceiling for automated analysis.