Note that TM’s have three kinds of behavior:

1. enter a halt state (and accept)
2. crash -- no transition specified (and reject)
3. loop forever (and reject)

• recursive refers to the fact that such languages were thought by Turing to be definable by recursive definitions (see Chap. 3)
• enumerable refers to the fact that the sentences of any language accepted by a TM can be "enumerated", or listed, one by one (not shown here, but not hard to prove)

The TM that accepts L will:

• halt for input from L
• crash for input not in L

That is, the recursive languages are closed under complementation.

Proof:
Suppose we have a non-looping TM T that accepts L. Create a new TM T¢as follows:

1. Remove all HALT (accept) states.
2. Where transitions are missing (causing crashes), provide transitions to a new HALT (accept) state.
3. A crash caused by trying to move left from the beginning of the tape can easily be turned into a HALT (and accept) (see p. 538)

Proof:
Let T be the TM for L, and T¢ be the TM for L¢ . Given any input string x, here is a non-looping program for determining whether x is in L:

The idea is to construct a TM T₁ that will run T and T¢ on x "simultaneously" (by interleaving their instructions).

Think about how you would program this on an ordinary computer, which is nothing more than a "fancy" TM.

T₁ will operate as follows:
1. Do step 1 for T (i.e. move it from its start state)
2. Do step 1 for T¢ (move it from its start state)
3. Do step 2 for T
4. Do step 2 for T¢
etc. etc.

Eventually T or T¢ will halt and accept, because exactly one of the following is true:

• x is in L
• x is in L¢

T₁ is a TM that loops forever on no input, and accepts exactly the language L.  Hence, L is recursive.

Let T₁ and T₂ be the TM’s accepting L₁ and L₂. We construct a TM T that will accept L₁ È L₂ as follows:

T will alternate the steps of T₁ and T₂ as in the previous proof with the following outcomes:

If T₁ halts (accepts), then T will halt and accept.
If T₂ halts (accepts), T will halt and accept.
If T₁ and T₂ both crash, T will crash.
If T₁ and T₂ both loop, then T will (of course) loop.

Let T₁ and T₂ be the TM’s accepting L₁ and L₂. We construct a TM T that will accept L₁ Ç L₂ as follows:

(Step 1) run an input on T₁:

• if it accepts, go to step 2
• if it crashes, T will crash
• if it loops, T will (of course) loop

• if it accepts, T will accept
• if it crashes, T will crash
• if it loops, T will (of course) loop

It is possible to "encode" a TM as a sequence of symbols from some alphabet.  In fact, the set of such TM encodings is a regular set!

Example:

Note: for encodings, we will by convention always make the start state #1 and the halt (accept state) #2 (we can always assume at most one halt state).

A "table" version of this machine can be written as follows.
States are written in "unary" notation (e.g. 3 = 111)
 

old state	input	new state	new tape symbol	head move
1	a	111	b	R
1	b	1	b	R
111	a	111	b	L
111	D	11	b	L

This table completely specifies the behavior of the TM. Now we can encode each row as a string:

Row 1: 1a111bR                                    note the form: 1⁺(a+b) 1⁺(a+b)(R+L)

The whole machine has the encoding:

One can imagine a list of all such encodings (for given tape alphabets), from smallest to largest and in lexicographic order. We will refer to this as an enumeration of all TM’s.

There are languages that cannot be recognized by any TM. Consider the following rectangular array.

• down the left side: an enumeration of all TM’s
• across the top, an enumeration of all input strings by length and lexicographic order
• entries of the array: whether of not the machine Accepts or Rejects the corresponding string (shown here for only the diagonal)

Now define L₁ = all x_i such that T_i rejects x_i.  For our example, it would be:

Now is L₁ r.e.? That is, is there some T_i that accepts L₁?

Suppose T_k (see above) accepts L₁. Consider x_k.

• if x_k ÎL₁, then
• T_k accepts x_k (by definition of "x_kÎL₁")
• and x_k ÏL₁ (by definition of L₁)
• if x_k ÏL₁, then
• T_k rejects x_k (by definition of "x_k ÏL₁")
• and x_k ÎL₁ (by definition of L₁)

Can one write a program (or TM = T_H) that can determine whether or not any other program will loop forever on any given input? Let’s see what happens if such a machine T_H exists.

We will incorporate T_H into a new program T, whose inputs will be x₁, x₂, …:

Here is what T will be programmed to do on input x_i:

run T_H for (T_i with input x_i) to determine whether it loops

This is a contradiction, because L₁ is not r.e. !!

Consider again:
 

	x1	x2	x3	x4	…	xk	…
T1	A
T2		R
T3			R
T4				A
…					…
Tk						A or R?
…

and let L₂ = L₁¢= { x_i | T_i accepts x_i}.

Part 1: L₂ is r.e.
We construct a program (TM = T) that proves it. Here is what T does on input x_i:

Part 2: L₂ is not recursive.
If it were, its complement L₁ would be recursive. But L₁ is not even r.e. Contradiction, so it’s not recursive.