## Universal TM / Halting Problem

### Church/Turing Thesis

The Church/Turing thesis says that anything which is algorithmically computable can be computed by a Turing machine. The weight toward this argument is everything that we've done up to this point in terms of TM extensions, grammatical generation, etc., is equivalent to what can be done with a standard 1-tape Turing Machine.

Another argument in the ability of a TM to act not just like a machine, i.e. hardware, but also like software, i.e., like a program run on a machine. The machine which runs other TMs is called a universal Turing Machine. An analogous idea is being asked to write Java interpreter program which can run any Java program along with some input. If we do so then we our interpreter could "run itself" if given another Java program as the input. This ability to "run yourself" will be the source of the first undecidable problem called the Halting problem. Obscure as it may seem, it is the source of other undecidable problems which are not at all obscure.

### TM Encodings

This is a sketch of the ideas used to create the Universal Turing Machine and prove the Halting Problem. The details of the encodings are found in the TM encoding details section below.

#### Use Universal Symbol and State Sets

Assume:
• There is an infinite symbol set, Σ, including all symbol we ever want to use:
```#, >, L, R, 1, c, a, b, Y, N, ...
```
• There is an infinite state set K.
Any TM M = (K,Σ,δ,s,H) draws from these sets, i.e.
```Σ ⊆ Σ∞  a finite subset
K ⊆ K∞  a finite subset
```
Enumerate these symbols and states by assigning arbitrary unary numbers to each, via an enumerator function N. for example,
N(#)=1N(>)=11N(L)=111N(R)=1111N(1)=11111N(c)=111111N(a)=1111111N(b)=11111111,  ...

#### A TM can run on any string in any finite alphabet Σ

A TM M = (K,Σ,δ,s,H) expects δ to be a function, but if you think of it as a partial function, the meaning is that that it "runs forever" if it reads a symbol σ ∈ Σ for which the transition δ(p,σ) is undefined. We have already discussed this issue in the TM Computations document. For example, suppose we have this partial TM:
({s,p,h}, {a,b,#,>}, δ, s, {h})
Here is how we could complete it, adding a "dead" (run forever) state:

#### 2-symbol encoding of strings

Pick an alphabet of two symbols in Σ. We will use the alphabet {1,c} where 1 is the unary digit symbol already used for the enumerator function N. The encoding function, E, which we want to create maps into strings in {1,c}*.

Strings in Σ* can be encoded by using c as a separator of symbol numbers. A string
```w = σ1σ2...σn
```
has the encoding:
```E(w) = cN(σ1)cN(σ2)...cN(σn)
```
For example,
```E(>#) = c11c1
```

#### 2-symbol encoding of a Turing Machine

Even if δ is a partial function, we can complete it, getting a true function.
```δ: K × Σ  →  K × (Σ ∪ {L,R})
```
Then ascertain that:
• A TM transition ( (p,a), (q,b) ), b ∈ Σ∪{L,R} can be encoded by a string in {1,c}*. Since both states and symbols are encoded as unary numbers, it's just a matter of effectively using the c to separate the parts like this:
```cN(p)cN(a)cN(q)cN(b)
```
• The transition function δ can be encoded as E(δ) by putting together the list the encoded transitions. At this point since δ is a complete function, you can determine the halt states: h is a halt state if it appears on the right side of a transition:
```( (__,__), (h,__) )
```
but NOT on the left side:
```( (h,__), (__,__) )
```
• A TM M = (K,Σ,δ,s,H) is encoded by putting together the encoded start state E(s) with the encoded transition function, E(δ). We can infer the full state set, K, the full symbol set, Σ, as well as the halt state set, H.
The encoding of a TM M, composed of E(s) and E(δ), is written as (see detail section below):
```E(M) = E(s)E(δ)cc
```
It turns out that the set of encodings of TMs is a decidable language. The basic format TM encodings gives a regular language. The encoding of E(δ) has the form:
```(c1+c1+c1+c1+)*
```
with transitions like this, for A,B,X,Y ∈ 1+:
```cAcBcXcY
```
The fact that these transitions make a function is beyond simply being regular; it implies that:
• The encoded full state set K is set of all A's and X's.
• The encoded non-halting state set K-H is set of all A's
• The encoded symbol set, Σ, is set of all B's
• There must be a transition for each (A,B) ∈ K-H × Σ
• There are not two transitions with same (A,B) values.
Determining whether a given string in (c1+c1+c1+c1+)* satisfies these requirements is decidable. Say to yourself: could I program it? The answer is yes (hopefully), although it may be tedious to do so. Lists of numbers can be stored on a single tape.

#### A TM can run on its own encoding

This is the "uroboros" effect: a TM running itself. Given M = (K,Σ,δ,s,H), if {1,c} ⊈ Σ, then M will most likely run forever on its own encoding because it will encounter symbols for which it is not defined. However, if {1,c} ⊆ Σ then the behavior is unpredictable. This is not as ridiculous as it first may seem. For example, if the TM decides strings defined over our favorite 2-letter alphabet {a,b}, then it could easily be "mapped" to an equivalent TM which decides strings over {1,c}.

Running a TM on it own encoding is the essence of what proves the Halting Problem. In particular, we consider whether:
``` M↓E(M)   M halts on its own encoding
```
or
``` M↑E(M)   M runs forever on its own encoding
```

#### 2-symbol encodings of TM/string pairs

Both strings and TMs can be encoded. We can put together the two encodings to create the encoding of a TM/string pair, written:
```E(M,w) = E(M)E(w)
```
As in other encodings parts, you can computationally:
• Decide if a string x = E(M,w) for some M and w
• Separate TM part, E(M), from the input string part, E(w).

### Universal Turing Machine

The universal TM, U, is a TM which takes as input an encoded machine/string pair, (M,w), and performs the actions of M running with input string w. The most important achievement is to simulate the accepting (i.e., halting) behavior of M. That is we want:
M halts on w   if and only if   U halts on E(M,w)
or, in notational terms,
```M↓w  if and only if  U↓E(M,w)
```
The input alphabet for U is {1,c}, and so it is legitimate to start U in any configuration:
```>#x     x ∈ {1,c}*
```
The first step is to decide whether x is of the right form E(M,w). If not, we make U run forever.

Otherwise assume U's start configuration is:
```>#E(M,w)
```
Make U be a 3-tape TM with these intended tape usages:
• tape 1: simulated tape contents
• tape 2: encoded transition function, never changed
• tape 3: encoded current state

#### Initialization

The initialization separates the encoded pair E(M,w) into it the encoded string E(w) and machine, E(M). E(M) is then separated into encode transition function and start state number E(δ) and N(s). These parts are written onto the 3 tapes like this:
• tape 1: >E(>#w): the encoded starting tape
• tape 2: >#E(δ): the encoded the transitions
• tape 3: >#N(s): the encoded start state

#### String Encoding on Tape 1

We need to say more about the tape 1 encoding. Assuming N(#)=1 and N(>)=11, the encoding of the initial part of the tape string ">#" is "c11c1", and so it is not immediately obvious what it means for # to be the "selected" symbol.

The idea is that the scan head should always be positioned at the "c" which precedes the selected symbol's unary encoding. Thus the ecoding of the initial simulation contents
```>#w
```
appears on the Universal machine as:
```>c11c1E(w)
```
During the simulation of M, the scan head of tape 1 consistently marks the "c" of the encoded symbol which is selected. For example, if the first step in M is to move left, then the resulting configuration on tape 1 after the simulated step would be:
```>c11c1E(w)
```

#### Real and Encoded

Keep in mind that there is both a real left end, >, and an encoded left end, N(>) = 11. U will never see the real left end because M cannot go left of the encoded left end.

There also are real blanks beyond the encoded portion (which would not be explicitly expressed in the initial configuration):
```>c11c1E(w)###....
```
Unlike the real left end, we may encounter a real blank when moving right beyond the intial content. In that case the U machine replaces the real blank by an encoded blank appended to the current tape string, "c1". The simulation section below mentions this point.

#### Run the Simulation

After the initialization, start simulating M's behavior as follows.
1. Reading from tapes 1 and 3, let
• A be the unary state number on tape 3, initially N(s)
• B be the selected unary symbol number on tape 1
Scan the encoded transitions on tape 2 looking for a match of the first pair of the encoded transition
```( (A,B), (X,Y) )
```
If a match of (A,B) is found, go to step 2.

If no match is not found, it can only be that A is the encoding of a halt state which has been reached by M, so halt U.
2. Simulate the transition:
1. change the encoded state on tape 3 from A to X
2. effect the change on tape 1 indicated by action Y:
1. if Y is the unary encoding of a symbol to write:
```...cBc...    ⊢U*    ...cYc...
```
This operation will require shifting the content of the tape right or left beyond the selected c. In either case you'll have to scan to the end of the content, which is marked by a real blank.
2. If Y is the encoding of an L or R symbol, then scan either left or right, respectively, to the adjacent "c" marker. For example, to going right is this:
```...cBcZ...   ⊢U*    ...cBcZ...
```
When going right, if we encounter a real blank, replace it by an encoded blank and select it, i.e., assuming N(#)=1,
```...cB   ⊢U*   ...cB#   ⊢U*   ...cBc1
```
3. Go back to step 1.

### The Halting Problem

The halting problem is this: given a TM M and input string w, is there an "algorithm" to decide whether M halts on input w or not? Assuming that an "algorithm" means a TM, the Universal TM allows us to frame this question in a formal context. Let HALT be the language of machine encoding pairs (M,w) where M halts on input w:
```HALT = { x ∈ {c,1}*: x = E(M,w) where M↓w }
```
HALT is precisely the language accepted by the Universal Turing Machine, U:
```M↓w  if and only if  U↓E(M,w)
```
Therefore HALT is recursively enumerable since it is accepted by U. The essence of the Halting problem is that HALT, which is recursively enumerable, or semi-decidable, is not recursive, i.e., not decidable.

#### Statement of the Halting Problem

Theorem: HALT is not recursive, or, undecidable, i.e., there is no algorithm which can determine whether an arbitrary TM, or an arbitrary algorithm, will halt on an arbitrary string input.

#### Proof

There are several facts going into the proof:
• If a language is recursive (decidable), then it is recursively enumerable (acceptable). Conversely, if it is not recursively enumerable, then it is not recursive.
• If a language is recursive, so is its complement. Conversely, if a language is not recursive, neither is the complement.
• If languages A and B are recursive, so is A ∪ B.
Conversely, if A ∪ B is not recursive then one of the components is not recursive.
Going further, if A ∪ B is not recursive and A is recursive, then B must not be recursive.
• The language over {1,c}* of TM encodings is recursive (decidable).
Here is the proof working backward directly from the cause. The textbook works forwards to get a contradiction.
1. Consider the language
```NOTRE = {E(M): M↑E(M)}
```
Saying it in English, NOTRE is the set of encodings of TMs which run forever on their own encodings.
2. Argue that NOTRE is not recursively enumerable, i.e., NOTRE cannot be accepted by any TM. Why? The proof uses a classic diagonalization construction.

Suppose NOTRE is recursively enumerable, i.e., it is the language accepted by a TM, M′.

Is E(M′) ∈ NOTRE   or   is E(M′) ∉ NOTRE ?
The contradiction is to argue that neither is possible:
```E(M′) ∈ NOTRE
⇔  M′↑E(M′)                (by definition of NOTRE)
⇔  M′ does not accept E(M′)   (by definition of acceptance by M′)
⇔  E(M′) ∉ NOTRE           (because NOTRE is the language accepted by M′)
```
The assumption that NOTRE is recursively enumerable must be false.
3. Conclude that NOTRE is not recursive (not R.E. implies not recursive).
4. Conclude that the complement, NOTRE = {E(M): M↓E(M)}, is not recursive (this is not the full set complement, but ignore this issue for now).
5. Conclude that the generalization, HALT = {E(M,w): M↓w}, is not recursive, because if we could decide this language for every TM M and every string w, then we decide it for the specific string w = E(M).
Step #4: complete Coming into step 4, we know that NOTRE is not recursive. We want to argue that {E(M): M↓E(M)} is not recursive. The correct complement of NOTRE is:
```NOTRE = {E(M): M↑E(M)} = {E(M): M↓E(M)} ∪ ENCTM
```
where
```ENCTM = {x ∈ {1,c}*: x is the encoding of a TM}
```
We have argued that ENCTM is recursive, implying that ENCTM is also recursive. But since
```NOTRE = {E(M): M↓E(M)} ∪ ENCTM
```
is not recursive, it must be true that {E(M): M↓E(M)} is not recursive.

#### Summary

1. The language HALT corresponding to the Halting problem is recursively enumerable, but not recursive. In particular, the universal TM accepts HALT, but no TM can decide HALT.
2. There are languages which are not recursively enumerable, in particular the language NOTRE in the proof.
3. Recursively enumerable languages are not closed under complementation. In particular, from the proof, the language NOTRE is not recursively enumerable, but its complement, NOTRE is recursively enumerable.

### Encoding details

The textbook suggests a certain encoding, but our encoding a bit more traditional. There is no point in trying make this encoding "useful", we simply want to ensure that it can be done in theory. Choose two dedicated symbols:
```1,c ∈ Σ∞
```
Assign every state and symbol a number which we can express in unary notation using the 1 symbol as the basis. Let
```N: K∞ ∪ Σ∞ → 1+
```
be the assignment of states and symbols to positive unary numbers. All known symbols must be assigned numbers:
```N(#) = 1, N(>) = 11, N(L) = 111, N(R) = 1111,
N(1) = 11111, N(c) = 111111
```
Writing "N(1) = 11111" looks confusing, but it simply means that 1 is the 5th symbol. We will describe our encoding function, E. It is necessary to encode strings and Turing machines.

#### String encodings

A string is a sequence of symbols:
```a1...an
```
The encoding is this:
```E(a1...an) = cN(a1)...cN(a1)
```
Consider the symbols a and b. We can assume their encodings are the next available numbers in the sequence.
```a = 1111111,  b = 11111111
```
And we encode "#ab" as follows:
```E(#ab) = c1c1111111c11111111
```
Thus the language of string encodings is precisely the regular language
```(c11*)* = (c1+)*
```
Furthermore, the encoding function is structure-preserving w.r.t. concatenation:
```E(ε) = ε
E(u·v) = E(u)·E(v)
```

#### TM Encodings

A Turing machine can express almost all of its information in the transition function alone where the transition function is an ordered list of transition quadruples of the form:
```(state, symbol, target_state, target_symbol)
```
Our textbook assumes that the start state is the first in this list, but we will make explicit mention of the start state. Otherwise, as in the textbook, we assume the halt state set H consists of those states which appear as a second state but never as a first. Thus a machine consists of a start state s and list of transitions:
```(s, (t1, t2, ..., tn))
```
To be a function means that there are no two different transitions
```ti = (q,a,pi,bi)  and  tj = (q,a,pj,bj)
```
Each state and symbol has an encoded numerical value which can be used to create an encoding of a transition t = (q,a,p,b) as follows:
```E(t) = cN(q)cN(a)cN(p)cN(b)
```
For example, assuming N(s) = 1, the encoding of the transition (s,>,s,R) is
```c1c1c1c1111
```
The encoding of a machine M = (s, (t1, t2, ..., tn)) is
```E(M) = N(s)E(t1)E(t2)...E(tn)cc
```
Thus the language of Turing Machine encodings is a subset of the regular language
```1+(c1+c1+c1+c1+)*cc
```
Consider the "a-writing machine" M which has these transitions:
```δ(s,#) = (h,a)
δ(s,>) = (h,R)
δ(s,a) = (h,a)
```
Also assuming N(s)=1, N(h)=11, and N(a)=1111111, then we can encode this machine as the string (spaces added for clarity only)
```1 c1c1c11c1111111 c1c1c11c1111 c1c1111111c11c1111111 cc
s (s,#,h, a)      (s,>,h, R)   (s,a,      h, a)
```
The textbook assumes that the transition quadruples are lexicographically ordered so that every TM has a unique code, but this "uniqueness" does not appear to be a crucial fact.

#### Machine/String pair encodings

Finally we want encodings of (M,w) pairs which can simply be the concatenation:
```E(M,w) = E(M)E(w)
```
Thus (machine,input) pair encodings belong to the regular language:
```1+(c1+c1+c1+c1+)*cc(c1+)*
```
For example, using the example machine in the above section with the input string w=ab, we get
```E(M,w) = 1c1c1c11c1111111c1c1c11c1111c1c1111111c11c1111111ccc1111111c11111111
```