Questions: Enumeration of Turing Machines and Index Sets

Question 1

Which of the following is an index set (as defined in computability theory)?

• A. W = {i : Mᵢ has exactly 7 states}
• B. W = {i : Mᵢ halts on input '0'}
• C. W = {i : the description of Mᵢ begins with the letter 'A'}
• D. W = {i : Mᵢ uses a binary tape alphabet}

Answer: (B)

An index set is defined by a property of the function computed by the machine, not by the machine's syntactic description or internal structure. 'Halts on input 0' is a property of the input-output behavior (does Mᵢ, when run on '0', eventually stop?), making it an index set — and by Rice's theorem, it is undecidable. Options A, C, and D are all syntactic properties about the machine's description or construction, not about the function it computes. If two machines Mᵢ and Mⱼ compute the same function but have different numbers of states or different tape alphabets, they would be treated differently by these syntactic properties — which disqualifies them as index sets.

Question 2

A software company claims to have built a tool that automatically detects whether any submitted program will go into an infinite loop on any input. According to Rice's theorem, what can be concluded about this claim?

• A. The tool is possible but only for programs written in restricted languages below Turing-complete power
• B. The tool is impossible for a general Turing-complete language — 'loops on some input' is a non-trivial index set and therefore undecidable
• C. The tool is possible because modern static analysis techniques can approximate the halting problem well enough
• D. The theorem only applies to theoretical Turing machines, not practical programming languages

Answer: (B)

Whether a program 'loops on at least one input' is a non-trivial semantic property: some programs have this property (any program with a while loop that may not terminate), and some do not (programs that always halt). It is an index set because it depends only on the function computed, not on the source code structure. Rice's theorem says all non-trivial index sets are undecidable, so no algorithm can decide this property for all programs in a Turing-complete language. Option A is correct that restricted languages (like terminating type systems) can provide guarantees, but the claim is about general programs. Option C confuses approximate heuristics (which may work on common cases but have guaranteed failures) with a decision procedure (which must work on all cases).

Question 3

The property 'Mᵢ has exactly 5 states' is an index set and therefore undecidable by Rice's theorem.

• T. True
• F. False

Answer: False

Rice's theorem applies only to index sets — properties of the *function computed* by the machine. 'Has exactly 5 states' is a syntactic property of the machine's description, not its behavior. Two machines that compute identical functions can have different numbers of states, so this property is not an index set. Syntactic/structural properties of machines are generally decidable: you can simply count the states in the description. Rice's theorem is silent about such properties. The theorem's power comes specifically from its focus on semantic (behavioral) properties.

Question 4

Rice's theorem implies that there can be no algorithm that reliably determines, for every program P and every property Q about P's output behavior, whether P has property Q.

• T. True
• F. False

Answer: True

This is precisely the import of Rice's theorem, stated in practical terms. Any non-trivial property of a program's output behavior — halting, accepting a specific input, computing a specific function, producing any output at all — defines a non-trivial index set and is therefore undecidable. There is no general-purpose semantic program analyzer. This is not a statement about difficulty or computational resources; it is a statement about impossibility. Approximate analyses (linters, type checkers, abstract interpretation) can be sound (conservative) or complete (aggressive) but never both general and exact.

Question 5

What is the distinction between an index set and a non-index-set property of Turing machines, and why does this distinction determine whether Rice's theorem applies?

Model answer: A property is an index set if, whenever two machines Mᵢ and Mⱼ compute the same function (same input-output behavior), they either both have the property or both lack it. In other words: the property depends only on WHAT the machine computes, not HOW it is constructed. Examples of index set properties: 'halts on all inputs,' 'computes the constant function 0,' 'accepts the empty string.' Non-index-set properties are structural/syntactic: 'has 5 states,' 'uses a binary alphabet,' 'has a specific transition from state q₁.' Rice's theorem applies only to index sets because its proof works by reducing the Halting Problem to any non-trivial index set property — a reduction that only works when the property is behavioral, not structural.

This distinction is the crux of the topic. Students who conflate 'any property of a Turing machine is undecidable' with Rice's theorem misapply it. The theorem is about semantic properties of the computed function; syntactic properties can be decided by inspecting the machine description. Understanding the boundary between the two lets students correctly identify when Rice's theorem provides an undecidability proof.