May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
1
Simulation ofTinL
The next thing we want to prove is the following:Theorem 6.1:If there is a Post-Turing program that computes the partial function f(x1, …, xm), then f is partially computable.Since our definition of partial computability is based on the languageL, this theorem states the following:If the m-ary partial function f on A* is computed by a program ofT, then there is a program ofLthat computes f (using base n values of strings).
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
2
Simulation ofTinL
Based on Theorem 6.1 and also Theorems 3.2 and 5.1, we can derive another Theorem:Theorem 6.2:Let f be an m-ary partial function on A*, where A is an alphabet of n symbols. Then the following conditions are all equivalent:1. f is partially computable;2. f is partially computable inLn;3. f is computed strictly by a Post-Turing program;4. f is computed by a Post-Turing program.The fact that there are so many equivalent notions of computability constitutes important evidence for the correctness of Church’s Thesis.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
3
Simulation ofTinL
For the proof of Theorem 6.1, let us now consider an m-ary partial function on N.Corollary 6.3:For any n, l 1, an m-ary partial function f on N is partially computable inLnif and only if it is also partially computable inLl.Proof:Each of these conditions is equivalent to the function f being partially computable.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
4
Simulation ofTinL
Considering the languageL1, we have:Corollary 6.4:Every partially computable function is computed strictly by some Post-Turing program that uses only the symbols s0and s1.Proof:This follows immediately from the fact that we can simulateLninT, as shown before.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
5
Simulation ofTinL
Now letPbe a Post-Turing program that computes f.We want to construct a programQin the languageLthat computes f.Qwill consist of three sections:BEGINNINGMIDDLEENDThe MIDDLE section will simulatePin a step-by-step “interpretive” manner.The BEGINNING section will arrange the input toQin the appropriate format for MIDDLE.The END section will extract the output.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
6
Simulation ofTinL
Let f be an m-ary partial function on A*, where A ={s1, …, sn}.The Post-Turing programPwill also use the blank B and perhaps other symbols sn+1, …, sr(we are not assuming that the computation is strict).We write the symbols thatPuses in the following order:s1, …, sn,sn+1, …, sr, B.The programQwill simulatePby using the numbers that strings on this alphabet represent in base r + 1 as “codes” for the corresponding strings.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
7
Simulation ofTinL
Note that we will write the blank as sr+1instead of s0.The current tape configuration will be kept track of byQusing three numbers stored in the variables L, H, and R.H will contain the numerical value of the symbol currently being scanned by the head.L will contain a number that represents in base r + 1a string of symbols w such that the tape contents to the left of the head consists of infinitely many blanks followed by w.R will contain a number that represents in a similar manner the string of symbols to the right of the string.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
8
Simulation ofTinL
Example:Consider the following tape configuration for r = 3(so we will use base 4):… B B B s1s3s2B s1s2B B B …Obviously, H = 2.L = 1·4 + 3 = 7R = 4·42+ 1·4 + 2 = 70 (remember that B = sr+1)
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
9
Simulation ofTinL
We are now able to simulate all of the instruction types ofTby programs ofL.As usual, we will specify how to simulate each type of instruction.An instructionPRINT siis simulated inLbyH iAn instructionIF siGOTO Lis simulated inLbyIF H = i GOTO L
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
10
Simulation ofTinL
An instructionRIGHTis simulated inLbyL CONCATr+1(L, H)H LTENDr+1(R)R LTRUNCr+1(R)IF R 0 GOTO ER r + 1// if R = 0, then there is a blank// (sr+1) to the right of the head
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
11
Simulation ofTinL
An instructionLEFTis simulated inLbyR CONCATr+1(H, R)H RTENDr+1(L)L RTRUNCr+1(L)IF L 0 GOTO EL r + 1// if L = 0, then there is a blank// (sr+1) to the left of the head
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
12
Simulation ofTinL
Now theMIDDLEsection ofQcan be generated by replacing each instruction inPby its simulation.When we writeBEGINNINGandEND, we must consider the following:f is an m-ary function on {s1, …, sn}*.Thus the initial values of X1, …, XmforQare numbers that represent the input strings in base n.However, the computations inQassume a base r + 1 representation of the input strings.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
13
Simulation ofTinL
Fortunately, we have Theorem 1.1 of Chapter 5, which tells us that the functions UPCHANGEn,land DOWNCHANGEn,lare computable.Now we can develop theBEGINNINGsection.Its task is to calculate the initial values of L, H, and R, which represent the initial tape configurationB x1B x2B … B xm,where the numbers x1, …, xmare represented inbase n notation.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
14
Simulation ofTinL
TheBEGINNINGsection then looks like this:L r + 1H r + 1Z1 UPCHANGEn,r+1(X1)Z2 UPCHANGEn,r+1(X2):Zm UPCHANGEn,r+1(Xm)R CONCATr+1(Z1, r + 1, Z2, r + 1, …, r + 1, Zm)
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
15
Simulation ofTinL
Now let us write theENDsection.It is supposed to put the output of the simulated program in base n representation into variable Y.Since we are not demanding a strict computation byP, the output is the concatenation of all symbols on the tape that belong to the alphabet A = {s1, …, sn}.Therefore, ourENDsection is written as follows:Z CONCATr+1(L, H, R)Y DOWNCHANGEn,r+1(Z)(Remember that DOWNCHANGEn,r+1automatically removes all symbols sn+1, …, sr+1).
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
16
Turing Machines
Actually, Turing’s original model of a computer was different from the Post-Turing language.We will now look at a model that is closer to Turing’s original idea, theTuring machine.Its main difference to the Post-Turing language is that it does not read a list of instructions, but it is defined by a finite number ofinternal statesandtransitionsbetween them.The machine’s next state is always determined by its current state and the current symbol under the head.Each transition also includesprinting a symbolormoving the headone square to the left or right.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
17
Turing Machines
The states are represented by the symbols q1, q2, q3, …,and the symbols that can appear on the tape are written as s0, s1, s2, …, where as usual s0= B is the blank.Expressions of one of the following three forms will be referred to asquadruples:1. qisjskql2. qisjR ql3. qisjL qlThey indicate that if when we are in state qiand the current symbol under the head is sj, the machine goes into state qland1. prints symbol skat the current head position,2. moves the head one square to the right, or3. moves the head one square to the left.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
18
Turing Machines
We now define aTuring machineto be a finite set of quadruples, no two of which begin with the same pairqisj.This means that at any time during the computation there isno ambiguityabout the next action to be performed.A Turing Machine without this requirement is called anondeterministicTuring machine.In this course, however, we will only considerdeterministicTuring machines.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
19
Turing Machines
Thealphabetof a given Turing machineMconsists of all the symbols siwhich occur in quadruples ofMexcept the symbol s0.A Turing machinebeginsits computation in state q1.A Turing machinehaltsif it is in state qi, scans the symbol sj, and does not have a quadruple that begins with qisj.We use the same conventions with regard toinputandoutputas we did for Post-Turing programs.So it should be clear what it means to say that some given Turing machineMcomputes a partial function f on A* for a given alphabet A.
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
20
Turing Machines
Just as for Post-Turing programs, we may speak of a Turing machineMto compute a functionstrictly.IfMcomputes f, where f is a partial function on A*, we say thatMcomputes f strictly if1. the alphabet ofMis a subset of A and2. wheneverMhalts, the final configuration has theform:Byqi(We indicate the current state of a Turing machine by writing the state symbol below the arrow.)
May 7, 2019
Theory of Computation Lecture 23: Turing Machines III
21
Turing Machines
Example:Consider the following Turing machine with alphabet A = {1} (we will write s0= B and s1= 1):q1B R q2q21 R q2q2B 1 q3q31 R q3q3B 1 q1
We can also represent the machine by a state transition diagram…
q1
q2
q3
B/R
1/R
B/1
1/R
B/1
Exit
1
… or a table:q1q2q3B1
R q2
1 q3
R q2
1 q1
R q3
0
Embed
Upload