Turing Machines, Undecidable and Unthinkable Problems

From Problem to Language

Assume a problem, formulated as a yes/no question, can be encoded as a structured sequence of symbols; a different encoding for each problem instance. The language corresponding to the problem is the set of encoded problem instances that yield an answer of yes. The problem might be primality testing, each instance a binary integer, and the language the set of prime numbers.

Undecidable and Unthinkable Problems

A problem is unthinkable if there is no tm that accepts the language. The problem is so hard you can't even think about it.

The problem is undecidable if the language is re, but not recursive. A tm can tell you if the answer is yes, if you wait long enough, but if the answer is no, you might wait forever. A decision is not guaranteed, hence the problem is undecidable.

The Empty Language

Here is an interesting problem. Given a tm, does it accept any words at all?

Let le be the language of strings that encode empty tms, where an empty tm accepts no input strings. The language le also includes strings that do not encode turing machines.

Let lne be the set of encoded nonempty tms. These are turing machines that accept at least one word. Note that le and lne are complementary.

A modified universal tm can simulate any other tm on all possible words in parallel, and watch for success. We did this before when generating the language. Therefore lne is re.

Suppose le is recursive. Given any tmi and word wj, construct a new tm that simulates tmi on wj internally, and ignores any external input string it is given. It reports success (accepting every string) if tmi accepts wj, and it accepts nothing if tmi does not accept wj. Thus if le is recursive, so is lu, which is a contradiction. Therefore le is not recursive, and lne can't be recursive either. We must have lne is re and le is not re.

Does a given tm accept any words? That problem is undecidable. Does a given tm accept nothing? That problem is unthinkable.

An empty tm excepts nothing, and a full tm accepts everything. Since le is the language of empty or invalid turing machines, let lf be the language of full turing machines. A string in lf encodes a tm that accepts every word. We showed above that le recursive implies lu recursive. The same proof shows lf recursive implies lu recursive. Therefore lf is not recursive. It may not even be re.

Details

When describing procedures that translate machines into other machines with desired properties, it is important to realize the amount of work being glossed over. To relate le to lu, a tm m1 is constructed to do the following. Given an encoded tm m2 and a word w, m1 builds a new tm m3 (encoded), such that m3 runs m2 on w regardless of input. It then simulates m4 on m3, where m4 is the presupposed recursive tm for le. Thus the universal tm is part of m1, enabling it to run m4. When m4 reports success or failure, m1 stops and reports same. To be rigorous, a full description of m1 would have to be given, and the properties of m1 verified. I'll pass. You get the idea.

The Halting Problem

You are given a computer program, and you are asked to predict its behavior. Let's start with the simplest question - does the program terminate? If the programming language is comparable in power to a tm, it is not possible to answer this question.

Given a tm, modify it, so it enters an infinite loop if it reaches a failure state or falls off the left end. The modified tm accepts its input iff it halts. Given tmi and wj, modify tmi as above, build a machine that runs tmi on wj, regardless of input, and analyze that machine to see if it halts. This makes lu recursive, which is a contradiction. The halting problem is re, since we can always run the machine and see if it stops. Thus the halting problem is undecidable.

A variation on the above provides only a tm, and asks whether there is any word that will cause it to halt. Again, we can try all words in parallel, so the problem is re. If it is recursive, then we can tell whether tmi halts on any input - whether it accepts any words - whether it belongs to lne. Yet lne is not recursive, as shown earlier. Asking whether a tm halts, ever, for any input, is undecidable.

A similar proof based on lf shows that asking whether a tm halts on every word is not recursive. I'm not even sure if it's re.

What Kind of Language

Given a tm, is its language recursive? I'm not asking whether that particular tm is recursive; I'm asking whether the language accepted by that tm is recursive, perhaps via some other tm that always halts.

Let lr be the language of encoded tms that implement recursive languages, and let lnr be its complement. Note that lnr includes all strings that are not proper turing machines.

Suppose lr is re. Here we go with the meta machines. Let m4 be a tm that recognizes lr. Let m1 do the following. Given any tm m2 and any word w, build m3 to run m2 on w, and when m2 succeeds, m3 looks at its input string, which it has ignored up to now. The input is a turing machine and a word, and m3 runs the universal tm on this combination. Finally, simulate m4 on m3. If m4 succeeds, m1 halts and reports success. This happens only if m3 implements a recursive language. Well m3 is a valid tm, so we passed that hurdle. If m2 accepts w then m3 implements lu, which is not recursive. If m2 does not accept w then m3 accepts no words at all, which is a recursive language. Thus m4 reports success only if m2 does not accept w. This makes m1 a tm for the complement of lu, yet the complement of lu is not re, so we have a contradiction. Since m1 cannot exist, m4 cannot exist either, and lr is not re. Asking whether a tm implements a recursive language is unthinkable.

Suppose lnr is re. Again, m2 and w are converted into m3, but m3 runs m2 on w and the universal tm on its input in parallel. If m2 accepts w, the language of m3 is all strings (recursive), otherwise it is lu (not recursive). Feed m3 to m4, and we have an m1 that accepts the complement of lu. Neither lr nor lnr is accepted by a tm, even though they are well defined complementary languages.

consider a well defined subset of recursive languages, such as regular languages. Clearly lu is not regular. also, the empty language, and the language of all strings, are both regular. Apply the above proof. Asking whether the language of a tm is regular, or not regular, is unthinkable. The same holds for context free, context sensitive, and so on.

Suppose m4 can tell if a tm defines a finite language. Let m3 run m2 on w, regardless of any input to m3. Now m3 accepts everything if m2 accepts w, and nothing if m2 does not accept w. Since nothing is finite, m4 reports success if m2 does not accept w. Thus m1 implements the complement of lu, which is impossible. Asking whether the language of a tm is finite is unthinkable.

If m4 accepts tms with infinite languages, let m3 simulate m2 on w while it counts moves. It also measures the length of its own input, which has nothing to do with m2 running on w. If the number of steps taken by m2 on w, before m2 accepts, exceeds the length of the input to m3, m3 accepts. If m2 fails, m3 accepts. Thus the language of m3 is infinite iff m2 does not acccept w. This is reported to us by m4. Thus m1 accepts the complement of lu, a contradiction. Asking whether the language of a tm is infinite is unthinkable.

You may have noticed a trend. A question regarding the behavior of a tm, e.g. the halting problem, is often undecidable, while questions surrounding the language of a tm are unthinkable.