Turing Machines, Universal TM, Universal Language

Universal TM

The universal tm is a tm that takes as input the encoded version of another tm, followed by an input string. The universal tm simulates the given tm on the given string, and halts if the simulated tm halts. A detailed description of the encoding, and the simulation, is provided in another section. For now, let's just say that it can be done.

Universal Language

The universal language l_u is the set of tm/input pairs that cause the universal tm to halt and report success. This language is re.

A Language that is Not RE

By definition, a language is suppose to be a set. Well an re language comes from a grammar, and is therefore a set. Its complement will also be a set. In other words, the complement of a re language is indeed a language. We will use this to build a language that is not re.

Once encoded, tms can be sorted, just as words can be sorted, and we may ask whether the i^th tm accepts the j^th binary word.

Let l₁ be the set of words w_i that are accepted by tm_i. Given a word w_i, reverse engineer it to find its index i. If w_i is written in binary, this is a straightforward process. The index of the empty word is 0. The index of 0 is 1 and the index of 1 is 2. The index of 00 is 3 and the index of 01 is 4, and so on. Next, generate one valid tm after another, until you find the i^th tm. Finally, invoke the universal tm on tm_i and w_i. The entire procedure is re, hence l₁ is re.

Let l₂ be the complement of l₁. This is a valid language. Suppose l₂ is re. In particular, tm_j accepts l₂. It accepts w_j iff it does not accept w_j, which is a contradiction. Therefore l₂ is not re. this language acts as the cornerstone of many important theorems.

The Universal Language is Not Recursive

Suppose l_u is recursive. We can tell in a finite amount of time whether any tm accepts any word, and more specifically, we can tell whether tm_i accepts w_i. This is the definition of l₁, described above. Thus l₁ is recursive, and so is its complement l₂. However, l₂ isn't even re. Therefore l_u is re but not recursive, and its complement is not re.

A Recursive Language that is Not Context Sensitive

Earlier I asserted the existence of recursive languages that are not context sensitive. Let's prove that now. This is another diagonalization argument, similar to the one shown above.

Context sensitive lenguages come from context sensitive grammars, which can be generated in order. Let m₁ crank out context sensitive grammars, and convert them into the corresponding bounded turing machines. We thus have a list of turing machines that accept context sensitive languages, and all the context sensitive languages are represented, often more than once.

Define a new language l as follows. Given a word w_i, find its index i, generate the i^th context sensitive grammar and the corresponding turing machine, see if tm_i accepts w_i, and return the opposite.

Suppose l is context sensitive. Some tm_j on the list accepts l. It accepts w_j iff it does not accept w_j. This is a contradiction, hence l is not a context sensitive language.

Build a turing machine that accepts l. Find the index of the input word, generate the i^th context sensitive grammar in lexicographical order, convert it to a tm, and run the tm on the input word. Since every tm on the list is recursive, the process terminates. In other words, l is a recursive language.

We have built a language that is recursive, and not context sensitive, demonstrating proper containment.