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 1tape 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_{∞}.
Σ ⊆ Σ_{∞} a finite subset K ⊆ K_{∞} a finite subsetEnumerate these symbols and states by assigning arbitrary unary numbers to each, via an enumerator function N. for example,
N(#)=1,
N(>)=11,
N(L)=111,
N(R)=1111,
N(1)=11111,
N(c)=111111,
N(a)=1111111,
N(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:
2symbol 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 stringw = σ_{1}σ_{2}...σ_{n}has the encoding:
E(w) = cN(σ_{1})cN(σ_{2})...cN(σ_{n})For example,
E(>#) = c11c1
2symbol 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.
E(M) = E(s)E(δ)ccIt 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+:
cAcBcXcYThe 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 nonhalting state set KH 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) ∈ KH × Σ
 There are not two transitions with same (A,B) values.
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 2letter 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
2symbol 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 3tape 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>#wappears 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.
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
( (A,B), (X,Y) )
If a match of (A,B) is found, go to step 2. 
Simulate the transition:
 change the encoded state on tape 3 from A to X
 effect the change on tape 1 indicated by action Y:

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. 
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

if Y is the unary encoding of a symbol to write:
 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 semidecidable,
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).
 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. 
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.  Conclude that NOTRE is not recursive (not R.E. implies not recursive).
 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).
 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).
Summary
 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.
 There are languages which are not recursively enumerable, in particular the language NOTRE in the proof.
 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) = 111111Writing "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:a_{1}...a_{n}The encoding is this:
E(a_{1}...a_{n}) = cN(a_{1})...cN(a_{1})Consider the symbols a and b. We can assume their encodings are the next available numbers in the sequence.
a = 1111111, b = 11111111And we encode "#ab" as follows:
E(#ab) = c1c1111111c11111111Thus the language of string encodings is precisely the regular language
(c11*)* = (c1+)*Furthermore, the encoding function is structurepreserving 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, (t_{1}, t_{2}, ..., t_{n}))To be a function means that there are no two different transitions
t_{i} = (q,a,p_{i},b_{i}) and t_{j} = (q,a,p_{j},b_{j})
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
c1c1c1c1111The encoding of a machine M = (s, (t_{1}, t_{2}, ..., t_{n})) is
E(M) = N(s)E(t_{1})E(t_{2})...E(t_{n})ccThus the language of Turing Machine encodings is a subset of the regular language
1+(c1+c1+c1+c1+)*ccConsider the "awriting 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