SI342: Universal TMs and the Chuch-Turing Thesis

Reading: Sections 5.1 and 5.2 of Theory of Computing, A Gentle Introduction.
Homework: Printout the homework and answer the questions on that paper.

Church-Turing Thesis

Last class we showed that extending our Turing machine model to allow a 2-way infinite tape (i.e. a JFLAP machine) does not add to the model's computational power. People have dreamed up many other extensions: multiple tapes, multiple tape heads on each tape, random access Turing machines, memory grids instead of tapes, and so on. But each of these extensions can be simulated with our simple model, just as we simulated JFLAP's 2-way infinite tape, so that the computational power of the extended modles --- i.e. the languages that can be decided and semi-decided --- is just the same as our simple model.

No matter how we try to extend our TM model, it never seems to increase its computational power. In fact, other completely different computational models have been proposed, and none of them are any more powerful than our basic Turing machine. This leads to the Church-Turing Thesis which, roughly, says this: "If a Turing machine can't compute it, nothing can!"

More precisely, the Church-Turing Thesis says that a Turing machine can be taken as the definition of what it means to compute --- i.e. by definition what a TM computes is what's computable --- because any computational device can be simulated by a Turing machine. This is not a mathematical fact, it's a philosophical statement. It's a definition of a term (computable) which, otherwise is vague. In the next few classes, we'll show that there are problems that cannot be computed by Turing machines, which means there are problems that are "uncomputable".

Machines vs. Programs

Each Turing machine is a special purpose device. Every new problem we come across requires us to construct a different Turing machine. This is not the way our computers work. In our intro cs course, did you build a new computer for each new problem? Was there a "hello world" computer? No! We have one, general purpose computer. For each new problem we come across we create a new program, not a new machine. We'd like to do the same thing with Turing machines. We'd like to have a one general purpose, Universal Turing machine and use it to simulate all of those special purpose Turing machines we've been creating. To do that, however, the special purpose Turing machine must be encoded in symbols and given to the Universal machine as part of its input. So our big task is to figure out how to encode any and every turing machine in some fixed alphabet. We might as well fix the alphabet to the simplest one we know: {0,1}.

Encoding

Inside a real computer, everything eventually gets represented as a simple string of 0's and 1's. We're going to do the same thing with our Turing Machines. We won't be able to use ASCII encodings though, or even Unicode ... there's no limit on the number of different characters that could potentially appear on a Turing machine tape. So we'll use a different encoding.

To make things clear, let's fix names for every possible character, and while we're at it, every possible state. Let S = {a₀ , a₁ , a₂ , ...} be the set of all possible symbols for a machine. Let A = {q₀ , q₁ , q₂ , ...} be the set of all possible states for Turing Machines. Thus, any machine M = (Q,Σ,Γ,δ,s) will satisfy Σ ⊂ S and Q ⊂ A.

We'll let e be our "encoding function", which takes any object and encodes it as a string of zeros and ones. First let's look at characters:

e(□) = 0
e(a_i) = 0ⁱ⁺²

Next we'll come up with an encoding scheme for states ... including the halt state

e(h) = 0
e(q_i) = 0ⁱ⁺²

Finally we must encode the three possible moves of the tape head:

e(S) = 0
e(L) = 00
e(R) = 000

At this point, we have a scheme for encoding the building blocks of a machine, but the real heart of the machine is $\delta$. If transition $m$ in a TM is $\delta(p,a) = (q,b,D)$, we encode $m$ as \[e(m) = e(p)1e(a)1e(q)1e(b)1e(D)1\]

Now we can encode a Turing Machine. Let $T$ be a Turing Machine with initial state $q$ and ``transitions'' (i.e. values of $\delta$) $m_1,m_2,\ldots,m_k$ We encode $T$ as: \[e(T) = e(q)1e(m_1)1e(m_2)1\cdots e(m_k)1\]

Since we've come so far, I should also point out that we could encode an input string $z = a_{i_1} a_{i_2} \cdots a_{i_n}$ as: \[e(z) = 11e(a_{i_1})1 e(a_{i_2})1 \cdots e(a_{i_n})1\]

To summarize:

Encoding Turing machines:
Let {a0,a1,a2,...} be the set of all symbols (excluding □) that may appear on a TM tape.
Let {q0,q1,q2,...} be the set of all states (excluding h) that may be part of a TM.
Symbols, states and tape-head moves get encoded by the encoding function e as follows:

Symbols	States	Moves
$e(□) = 0$ $e(a_i) = 0^{i+2}$	$e(h) = 0$ $e(q_i) = 0^{i+2}$	$e(S) = 0$ $e(L) = 00$ $e(R) = 000$

The transition t := δ(p,x) = (q,y,m) gets encoded as: e(t) = e(p)1e(x)1e(q)1e(y)1e(m)1.
The machine T with start state q and transitions t1,t2,..., tk gets encoded as: e(T) = e(q)1e(t1)1e(t2)1...1e(tk)1.
Input z := a_i1 a_i2 ... a_in gets encoded as e(z) = 11e(a_i1)1e(a_i2)1 ... e(a_in)1.
Machine T and input z get encoded as e(T)e(z).

Note: The set of states in the machine is implicit in the transitions, meaning that if you want to know what states are in the TM described by an encoding, you go through all the transitions and collect any states that get mentioned into a set, and that's your set of states.

Note: You may be worried (or maybe not) that there could be "missing" transitions in the encoding, meaning that there is a state that is a part of the machine, since it appears in a transition, but does not itself have outgoing transisitions for each of the characters that get mentioned. We adopt the same convention as with our diagram: if $q_i$ is a state in the machine and $a_j$ a character in the tape alphabet for which there is no transition out of $q_i$ for symbol $a_j$, $\delta(q_i,a_j) = (q_i,a_j,S)$ is an implicit transition.

Example of Encoding Machines

Let T be the Turing Machine:

This machine gets encoded as:

0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1
\__/ \____________________________/  \______________________/
start        transition 1                 transition 2
state

Encoding Input

We'll want to encode both the special purpose machine and the input string it's supposed to compute with. Our convention for encoding the input string will be as follows:

Input string w = a_i₁ a_i₂ ... a_{i_k} gets encoded as e(w) = 11e(a_i₁ ) e(a_i₂ ) ... e(a_{i_k} )

This input string can then simply be appended to the encoded machine.

A Complete Example

Give the encoding of string w = a₀ a₀ a₀ and machine M:

0010010101010110010010001001000110001010001010001100010010010010001111001001001
   \_________/ \_______________/ \______________/ \_______________/ \_________/
        t1            t2                t3                t4           input

Recognizing an encoded TM+input

When we get around to creating a "Universal" Turing machine that can read an encoded TM+input and simulate that machine on that input, we'll have to be able to at least decide whether the input is a proper encoding according to the above rules. This is actually easier than you might think. Why? Because the language of all proper encodings is regular! Here's a regular expression for it:

00+1(00+10+10+10+1(0|00|000)11)*11(00+1)*

Christopher W Brown

Last modified: Sun Dec 6 22:51:13 EST 2009