Class 38: Encoding Turing Machines

Reading

Sections 5.1 and 5.2 of Theory of Computing, A Gentle Introduction.

Homework

Draw the machine and input encoded by

00010001001001001011000100010010100011001001001000100011001000100100100011001010101011110010001001
	

using the encoding scheme below. Simulate the machine on this input. What happens? Congrats. You are now a Universal Turing Machine!

Church-Turing Hypothesis

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 Hypothesis which, roughly, says this: "If a Turing machine can't compute it, nothing can!"

More precisely, the Church-Turing hypothesis 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 out 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 . If transition in a TM is , we encode as

Now we can encode a Turing Machine. Let T be a Turing Machine with initial state and ``transitions'' (i.e. values of ) . We encode as:

Since we've come so far, I should also point out that we could encode an input string as:

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_i1 a_i2 ... a_ik gets encoded as e(w) = 11e(a_i1 ) e(a_i2 ) ... e(a_ik )

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 language for it:

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