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 l_e be the language of strings that encode empty tms, where an empty tm accepts no input strings. The language l_e also includes strings that do not encode turing machines.

Let l_ne be the set of encoded nonempty tms. These are turing machines that accept at least one word. Note that l_e and l_ne 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 l_ne is re.

Suppose l_e is recursive. Given any tm_i and word w_j, construct a new tm that simulates tm_i on w_j internally, and ignores any external input string it is given. It reports success (accepting every string) if tm_i accepts w_j, and it accepts nothing if tm_i does not accept w_j. Thus if l_e is recursive, so is l_u, which is a contradiction. Therefore l_e is not recursive, and l_ne can't be recursive either. We must have l_ne is re and l_e 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 l_e is the language of empty or invalid turing machines, let l_f be the language of full turing machines. A string in l_f encodes a tm that accepts every word. We showed above that l_e recursive implies l_u recursive. The same proof shows l_f recursive implies l_u recursive. Therefore l_f 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 l_e to l_u, a tm m₁ is constructed to do the following. Given an encoded tm m₂ and a word w, m₁ builds a new tm m₃ (encoded), such that m₃ runs m₂ on w regardless of input. It then simulates m₄ on m₃, where m₄ is the presupposed recursive tm for l_e. Thus the universal tm is part of m₁, enabling it to run m₄. When m₄ reports success or failure, m₁ stops and reports same. To be rigorous, a full description of m₁ would have to be given, and the properties of m₁ 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 tm_i and w_j, modify tm_i as above, build a machine that runs tm_i on w_j, regardless of input, and analyze that machine to see if it halts. This makes l_u 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 tm_i halts on any input - whether it accepts any words - whether it belongs to l_ne. Yet l_ne is not recursive, as shown earlier. Asking whether a tm halts, ever, for any input, is undecidable.

A similar proof based on l_f 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 l_r be the language of encoded tms that implement recursive languages, and let l_nr be its complement. Note that l_nr includes all strings that are not proper turing machines.

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

Suppose l_nr is re. Again, m₂ and w are converted into m₃, but m₃ runs m₂ on w and the universal tm on its input in parallel. If m₂ accepts w, the language of m₃ is all strings (recursive), otherwise it is l_u (not recursive). Feed m₃ to m₄, and we have an m₁ that accepts the complement of l_u. Neither l_r nor l_nr 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 l_u 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 m₄ can tell if a tm defines a finite language. Let m₃ run m₂ on w, regardless of any input to m₃. Now m₃ accepts everything if m₂ accepts w, and nothing if m₂ does not accept w. Since nothing is finite, m₄ reports success if m₂ does not accept w. Thus m₁ implements the complement of l_u, which is impossible. Asking whether the language of a tm is finite is unthinkable.

If m₄ accepts tms with infinite languages, let m₃ simulate m₂ on w while it counts moves. It also measures the length of its own input, which has nothing to do with m₂ running on w. If the number of steps taken by m₂ on w, before m₂ accepts, exceeds the length of the input to m₃, m₃ accepts. If m₂ fails, m₃ accepts. Thus the language of m₃ is infinite iff m₂ does not acccept w. This is reported to us by m₄. Thus m₁ accepts the complement of l_u, 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.