Turing Machines, Rice's Theorem

Rice's Theorem

Let S3 be a subset of the re languages, possibly all of the re languages, and partition S3 into two nonempty subsets S1 and S2. Let a tm define a language that is known to lie in S3. One cannot look at the tm and place the language in S1 or S2. The task is undecidable, or unthinkable.

Assume, without loss of generality, that S2 contains the empty language.

Suppose m5, a recursive machine, looks at a tm and determines whether its language is in S1. Let m4 accept a particular language l1 in S1. We can do this because S1 is nonempty. Now m1 takes any tm m2 and word w and creates m3, such that m3 runs m2 on w, and then runs m4 on the input word passed to m3. If m2 accepts w then m3 accepts the language l1. If m2 does not accept w then m3 accepts no words, that is, the empty language. Either way, m3 lives in S3. When m5 looks at m3, it can tell whether m3 accepts l1 or nothing, because it can place m3 in S1 or S2. Therefore, m5 tells us whether m2 accepts w. This is reported by m1, and lu becomes recursive, which is a contradiction. Thus a tm lying in S3 cannot be assigned to S1 by a decidable process, and with S2 as complement, assigning a tm to S2 is not decidable either.

If assignment to S1 is re, then assignment to S2 cannot be, as the combination would create a recursive process.

Often S3 is the entire set of re languages, which is the assumption for the remainder of rice's theorem.

When Assignment to S1 is re

Is there an re procedure for determining whether the language of a tm is in S1? There is, iff the following conditions hold for every language l in S1. (Just to be clear, we are no longer making assumtions about the empty language; it could be in S1 or S2.)

  1. Every re superset of l is also in S1.

  2. If l is infinite, some finite subset of l is in S1.

  3. The set of finite languages in S1 can be generated.

First assume a procedure exists.

Suppose l1 lies in S1, while a superset l2 lies in S2. This is a violation of condition (1). Let m4 accept l1 and let m5 accept l2. Construct m3 so that m3 runs m2 on w and then runs m5 on its input, while running m4 on its input in parallel. Every word of l1 satisfies m4, and m3, while the words of l2-l1 satisfy m3 only when m2 accepts w. Thus m3 is a tm in S1 only if m2 does not accept w. A procedure indicates membership in S1, and when this is applied to m3, a turing machine accepts the complement of lu, which is a contradiction. Therefore condition (1) holds.

Suppose m4 recognizes a language l l in S1 that violates condition (2). In other words, every finite subset of l is in S2. Let m3 run m4 on its input, while running m2 on w. If m2 succeeds first, m3 fails, and the language of m3 becomes a finite subset of l, not in S1. Otherwise m3 accepts l, in S1. Once again, m3 ∈ S1 implies m2 does not accept w, and we have constructed a machine that accepts the complement of lu.

Now for condition (3). A tm can generate all the finite languages in a predefined order. The strings of a finite language add up to a finite length. Using some combinatorics and a stack, crank out languages of total length 0, 1, 2, 3, and so on. Given such a language, paste its words together with pipes in between to build a regular expression, then convert to an fsm. An fsm is a tm, so we have a machine that accepts the aforementioned finite language. Feed it to the S1 detector. In fact, we can feed all these state machines into the S1 detector in parallel, using a diagonal strategy. Whenever one is accepted, print out the "approved" fsm, and/or its language.

Conversely, assume all three conditions hold, and let m2 generate all the finite languages in S1. Since m2 is deterministic, it generates these languages in a particular order, though we can't say what that order is. Given any turing machine m1, let m3 run m1 on all the words in all the finite languages of S1 in parallel. This is another diagonal trick. Simulate m1 on each word in the first language for 1 step. Then simulate m1 on each word in the first two languages for two steps. Then simulate m1 on each word in the first three languages for three steps, and so on. If any of these languages is accepted by m1, we'll find out about it eventually. In fact m3 can systematically crank out all the finite languages of S1 that are accepted by m1. For our purposes, m3 can halt with success if any finite language of S1 is accepted by m1.

If m3 indicates success, the language of m1 is a superset of the aforementioned finite language, and by condition (1), the language of m1 belongs to S1. Conversely, if the language of m1 belongs to S1 then, by condition (2), the same is true of a finite sublanguage. (If the language is finite, let the sublanguage be the same language.) This sublanguage is accepted by m1, and m3 will find it, or some other finite sublanguage of m1, and report success. Therefore m3 has become our S1 detector.

Applications

With this theorem in hand, many of the earlier proofs can be simplified.

In the last section we proved there is no process to determine whether the language of a tm is regular. Let S1 be the set of regular languages, and take the union of any one of these languages with a context free language. The result is not regular, condition (1) fails, and there is no procedure. Similar results hold for context free languages, finite languages, infinite languages, and many other proper subsets of re languages.