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 lu 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 ith tm accepts the jth binary word.

Let l1 be the set of words wi that are accepted by tmi.  Given a word wi, reverse engineer it to find its index i.  If wi 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 ith tm.  Finally, invoke the universal tm on tmi and wi.  The entire procedure is re, hence l1 is re.

Let l2 be the complement of l1.  This is a valid language.  Suppose l2 is re.  In particular, tmj accepts l2.  It accepts wj iff it does not accept wj, which is a contradiction.  Therefore l2 is not re.  this language acts as the cornerstone of many important theorems.

The Universal Language is Not Recursive

Suppose lu is recursive.  We can tell in a finite amount of time whether any tm accepts any word, and more specifically, we can tell whether tmi accepts wi.  This is the definition of l1, described above.  Thus l1 is recursive, and so is its complement l2.  However, l2 isn't even re.  Therefore lu 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 m1 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 wi, find its index i, generate the ith context sensitive grammar and the corresponding turing machine, see if tmi accepts wi, and return the opposite.

Suppose l is context sensitive.  Some tmj on the list accepts l.  It accepts wj iff it does not accept wj.  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 ith 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.