1.2.MODELING COMPUTATION AND EFFICIENCY p1.5(15) 2.Read a bit (or possibly a symbol from a slightly larger alphabet,say a digit in the set 10,...,9))from the "scratch pad"or working space we allow the algorithm to use. Based on the values read, 3.Write a bit/symbol to the scratch pad. 4.Either stop and output 0 or 1,or choose a new rule from the set that will be applied next. Finally,the running time is the number of these basic operations performed. Below,we formalize all of these notions. 1.2.1 The Turing Machine The k-tape Turing machine is a concrete realization of the above informal notion,as follows(see Figure 1.1). Scratch Pad:The scratch pad consists of k tapes.A tape is an infinite one-directional line of cells,each of which can hold a symbol from a finite set I called the alphabet of the machine.Each tape is equipped with a tape head that can potentially read or write symbols to the tape one cell at a time.The machine's computation is divided into discrete time steps,and the head can move left or right one cell in each step. The first tape of the machine is designated as the input tape.The machine's head cancan only read symbols from that tape,not write them-a so-called read-only head. The k-1 read-write tapes are called work tapes and the last one of them is designated as the output tape of the machine,on which it writes its final answer before halting its computation. Finite set of operations/rules:The machine has a finite set of states,denoted Q.The machine contains a“register'”that can hold a single element of Q;this is the”state'”of the machine at that instant.This state determines its action at the next computational step,which consists of the following:(1)read the symbols in the cells directly under the k heads (2)for the k-1 read/write tapes replace each symbol with a new symbol(it has the option of not changing the tape by writing down the old symbol again),(3)change its register to contain another state from the finite set Q (it has the option not to change its state by choosing the old state again)and (4)move each head one cell to the left or to the right. One can think of the Turing machine as a simplified modern computer,with the machine's tape corresponding to a computer's memory,and the transition function and register corresponding to the computer's central processing unit (CPU).However,it's best to think of Turing machines as simply a formal way to describe algorithms.Even though algorithms are often best described by plain English text,it is sometimes useful to express them by such a formalism in order to argue about them mathematically.(Similarly,one needs to express an algorithm in a programming language in order to execute it on a computer.) Formal definition.Formally,a TM M is described by a tuple (T,Q,6)containing: Web draft2007-01-0821:59
DRAFT 1.2. MODELING COMPUTATION AND EFFICIENCY p1.5 (15) 2. Read a bit (or possibly a symbol from a slightly larger alphabet, say a digit in the set {0, . . . , 9}) from the “scratch pad” or working space we allow the algorithm to use. Based on the values read, 3. Write a bit/symbol to the scratch pad. 4. Either stop and output 0 or 1, or choose a new rule from the set that will be applied next. Finally, the running time is the number of these basic operations performed. Below, we formalize all of these notions. 1.2.1 The Turing Machine The k-tape Turing machine is a concrete realization of the above informal notion, as follows (see Figure 1.1). Scratch Pad: The scratch pad consists of k tapes. A tape is an infinite one-directional line of cells, each of which can hold a symbol from a finite set Γ called the alphabet of the machine. Each tape is equipped with a tape head that can potentially read or write symbols to the tape one cell at a time. The machine’s computation is divided into discrete time steps, and the head can move left or right one cell in each step. The first tape of the machine is designated as the input tape. The machine’s head can can only read symbols from that tape, not write them —a so-called read-only head. The k − 1 read-write tapes are called work tapes and the last one of them is designated as the output tape of the machine, on which it writes its final answer before halting its computation. Finite set of operations/rules: The machine has a finite set of states, denoted Q. The machine contains a “register” that can hold a single element of Q; this is the ”state” of the machine at that instant. This state determines its action at the next computational step, which consists of the following: (1) read the symbols in the cells directly under the k heads (2) for the k − 1 read/write tapes replace each symbol with a new symbol (it has the option of not changing the tape by writing down the old symbol again), (3) change its register to contain another state from the finite set Q (it has the option not to change its state by choosing the old state again) and (4) move each head one cell to the left or to the right. One can think of the Turing machine as a simplified modern computer, with the machine’s tape corresponding to a computer’s memory, and the transition function and register corresponding to the computer’s central processing unit (CPU). However, it’s best to think of Turing machines as simply a formal way to describe algorithms. Even though algorithms are often best described by plain English text, it is sometimes useful to express them by such a formalism in order to argue about them mathematically. (Similarly, one needs to express an algorithm in a programming language in order to execute it on a computer.) Formal definition. Formally, a TM M is described by a tuple (Γ, Q, δ) containing: Web draft 2007-01-08 21:59
p1.6(16) 1.2.MODELING COMPUTATION AND EFFICIENCY read only head 2o00110100010 100 0 Work tape 11010100o匹 read/write head Output tape 匹 Register Figure 1.1:A snapshot of the execution of a 3-tape Turing machine M with an input tape,a work tape,and an output tape. A set I of the symbols that M's tapes can contain.We assume that I contains a designated “blank”symbol,denoted☐，a designated“start'”symbol,denoted>and the numbers0and 1.We call I the alphabet of M. A set Q of possible states M's register can be in.We assume that Q contains a designated start state,denoted qstart and a designated halting state,denoted ghalt. A function 6:Qx TkQx Ik-1x fL,S,R)describing the rule M uses in performing each step.This function is called the transition function of M (see Figure 1.2.) IF THEN input work/ current move new move new symbol output state input work/ work/ state read tape head output output symbol tape tape read symbol 6 q b q Figure 1.2:The transition function of a two tape TM(i.e.,a TM with one input tape and one work/output tape). If the machine is in state qQ and (01,02,...,)are the symbols currently being read in the k tapes,and 6(q,(01,...,+1))=(q,(02,...,),z)where zE [L,SR)*then at the next step the o symbols in the last k-1 tapes will be replaced by the a'symbols,the machine will be in state Web draft2007-01-0821:59
DRAFT p1.6 (16) 1.2. MODELING COMPUTATION AND EFFICIENCY Input tape Work tape Output tape > 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 > 1 1 0 1 0 1 0 0 0 1 > 0 1 q Register 7 read only head read/write head read/write head Figure 1.1: A snapshot of the execution of a 3-tape Turing machine M with an input tape, a work tape, and an output tape. • A set Γ of the symbols that M’s tapes can contain. We assume that Γ contains a designated “blank” symbol, denoted , a designated “start” symbol, denoted B and the numbers 0 and 1. We call Γ the alphabet of M. • A set Q of possible states M’s register can be in. We assume that Q contains a designated start state, denoted qstart and a designated halting state, denoted qhalt. • A function δ :Q × Γ k → Q × Γ k−1 × {L, S, R} k describing the rule M uses in performing each step. This function is called the transition function of M (see Figure 1.2.) IF THEN input symbol read work/ output tape symbol read current state move input head new work/ output tape symbol move work/ output tape new state ... ... ... ... ... ... ... ... ... ... ... ... ... ... a b q b’ q’ Figure 1.2: The transition function of a two tape TM (i.e., a TM with one input tape and one work/output tape). If the machine is in state q ∈ Q and (σ1, σ2, . . . , σk) are the symbols currently being read in the k tapes, and δ(q,(σ1, . . . , σk+1)) = (q 0 ,(σ 0 2 , . . . , σ0 k ), z) where z ∈ {L, SR} k then at the next step the σ symbols in the last k − 1 tapes will be replaced by the σ 0 symbols, the machine will be in state Web draft 2007-01-08 21:59
1.2.MODELING COMPUTATION AND EFFICIENCY p1.7(17) g',and the k+1 heads will move Left,Right or Stay in place,as given by z.(If the machine tries to move left from the leftmost position of a tape then it will stay in place.) All tapes except for the input are initialized in their first location to the start symbol D and in all other locations to the blank symbol The input tape contains initially the start symbol D,a finite non-blank string ("the input"),and the rest of its cells are initialized with the blank symbol All heads start at the left ends of the tapes and the machine is in the special starting state qstart. This is called the start configuration of M on input z.Each step of the computation is performed by applying the function 6 as described above.The special halting state ghalt has the property that once the machine is in ghalt,the transition function 6 does not allow it to further modify the tape or change states.Clearly,if the machine enters ghalt then it has halted.In complexity theory we are typically only interested in machines that halt for every input in a finite number of steps. Now we formalize the notion of running time.As every non-trivial algorithm needs to at least read its entire input,by "quickly"we mean that the number of basic steps we use is small when considered as a function of the input length. DEFINITION 1.4 (COMPUTING A FUNCTION AND RUNNING TIME) Let f {0,1)*{0,1}*and let T N-N be some functions,and let M be a Turing machine.We say that M computes f in T(n)-time2 if for every r,1)", if M is initialized to the start configuration on input x,then after at most T() steps it halts with f(x)written on its output tape. We say that M computes f if it computes f in T(n)time for some function T:N- N. REMARK 1.5 (TIME-CONSTRUCTIBLE FUNCTIONS) We say that a function T:N-N is time constructible if T(n)>n and there is a TM M that computes the function xT()in time T(n).(As usual,T(),denotes the binary representation of the number T().) Examples for time-constructible functions are n,nlogn,n2,2".Almost all functions encoun- tered in this book will be time-constructible and,to avoid annoying anomalities,we will restrict our attention to time bounds of this form.(The restriction T(n)>n is to allow the algorithm time to read its input.) EXAMPLE 1.6 Let PAL be the Boolean function defined as follows:for every x {0,1)*,PAL(x)is equal to 1 if x is a palindrome and equal to 0 otherwise.That is,PAL(z)=1 if and only if x reads the same from left to right as from right to left (i.e.,z1x2...In =ZnEn-1...1).We now show a TM M that computes PAL within less than 3n steps. 2Formally we should write "T-time"instead of "T(n)-time",but we follow the convention of writing T(n)to emphasize that T is applied to the input length. Web draft2007-01-0821:59
DRAFT 1.2. MODELING COMPUTATION AND EFFICIENCY p1.7 (17) q 0 , and the k + 1 heads will move Left, Right or Stay in place, as given by z. (If the machine tries to move left from the leftmost position of a tape then it will stay in place.) All tapes except for the input are initialized in their first location to the start symbol B and in all other locations to the blank symbol . The input tape contains initially the start symbol B, a finite non-blank string (“the input”), and the rest of its cells are initialized with the blank symbol . All heads start at the left ends of the tapes and the machine is in the special starting state qstart. This is called the start configuration of M on input x. Each step of the computation is performed by applying the function δ as described above. The special halting state qhalt has the property that once the machine is in qhalt, the transition function δ does not allow it to further modify the tape or change states. Clearly, if the machine enters qhalt then it has halted. In complexity theory we are typically only interested in machines that halt for every input in a finite number of steps. Now we formalize the notion of running time. As every non-trivial algorithm needs to at least read its entire input, by “quickly” we mean that the number of basic steps we use is small when considered as a function of the input length. Definition 1.4 (Computing a function and running time) Let f : {0, 1} ∗ → {0, 1} ∗ and let T : N → N be some functions, and let M be a Turing machine. We say that M computes f in T(n)-time2 if for every x ∈ {0, 1} ∗ , if M is initialized to the start configuration on input x, then after at most T(|x|) steps it halts with f(x) written on its output tape. We say that M computes f if it computes f in T(n) time for some function T : N → N. Remark 1.5 (Time-constructible functions) We say that a function T : N → N is time constructible if T(n) ≥ n and there is a TM M that computes the function x 7→ xT(|x|)y in time T(n). (As usual, xT(|x|)y denotes the binary representation of the number T(|x|).) Examples for time-constructible functions are n, n log n, n 2 , 2n . Almost all functions encountered in this book will be time-constructible and, to avoid annoying anomalities, we will restrict our attention to time bounds of this form. (The restriction T(n) ≥ n is to allow the algorithm time to read its input.) Example 1.6 Let PAL be the Boolean function defined as follows: for every x ∈ {0, 1} ∗ , PAL(x) is equal to 1 if x is a palindrome and equal to 0 otherwise. That is, PAL(x) = 1 if and only if x reads the same from left to right as from right to left (i.e., x1x2 . . . xn = xnxn−1 . . . x1). We now show a TM M that computes PAL within less than 3n steps. 2Formally we should write “T-time” instead of “T(n)-time”, but we follow the convention of writing T(n) to emphasize that T is applied to the input length. Web draft 2007-01-08 21:59
pl.8(18) 1.2.MODELING COMPUTATION AND EFFICIENCY Our TM M will use 3 tapes (input,work and output)and the alphabet ,0,1).It operates as follows: 1.Copy the input to the read/write work tape. 2.Move the input head to the beginning of the input. 3.Move the input-tape head to the right while moving the work-tape head to the left.If at any moment the machine observes two different values,it halts and output 0. 4.Halt and output 1. We now describe the machine more formally:The TM M uses 5 states denoted by {qstart,qcopy,qright,qtest,ghalt. Its transition function is defined as follows: 1.On state qstart,move the input-tape head to the right,and move the work-tape head to the right while writing the start symbol change the state to gcopy.(Unless we mention this explicitly,the function does not change the output tape's contents or head position.) 2.On state qcopy: If the symbol read from the input tape is not the blank symbol then move both the input-tape and work-tape heads to the right,writing the symbol from the input-tape on the work-tape;stay in the state qcopy. If the symbol read from the input tape is the blank symbol then move the input-tape head to the left,while keeping the work-tape head in the same place (and not writing anything);change the state to qright. 3.On state gright: If the symbol read from the input tape is not the start symbol D then move the input- head to the left,keeping the work-tape head in the same place(and not writing anything); stay in the state gright. If the symbol read from the input tape is the start symbol D then move the input-tape to the right and the work-tape head to the left (not writing anything);change to the state qtest. 4.On state qtest: If the symbol read from the input-tape is the blank symbol and the symbol read from the work-tape is the start symbol D then write 1 on the output tape and change state to halt. Otherwise,if the symbols read from the input tape and the work tape are not the same then write 0 on the output tape and change state to ghalt. DRA Web draft2007-01-0821:59
DRAFT p1.8 (18) 1.2. MODELING COMPUTATION AND EFFICIENCY Our TM M will use 3 tapes (input, work and output) and the alphabet {B, , 0, 1}. It operates as follows: 1. Copy the input to the read/write work tape. 2. Move the input head to the beginning of the input. 3. Move the input-tape head to the right while moving the work-tape head to the left. If at any moment the machine observes two different values, it halts and output 0. 4. Halt and output 1. We now describe the machine more formally: The TM M uses 5 states denoted by {qstart, qcopy, qright, qtest, qhalt}. Its transition function is defined as follows: 1. On state qstart, move the input-tape head to the right, and move the work-tape head to the right while writing the start symbol B; change the state to qcopy. (Unless we mention this explicitly, the function does not change the output tape’s contents or head position.) 2. On state qcopy: • If the symbol read from the input tape is not the blank symbol then move both the input-tape and work-tape heads to the right, writing the symbol from the input-tape on the work-tape; stay in the state qcopy. • If the symbol read from the input tape is the blank symbol , then move the input-tape head to the left, while keeping the work-tape head in the same place (and not writing anything); change the state to qright. 3. On state qright: • If the symbol read from the input tape is not the start symbol B then move the inputhead to the left, keeping the work-tape head in the same place (and not writing anything); stay in the state qright. • If the symbol read from the input tape is the start symbol B then move the input-tape to the right and the work-tape head to the left (not writing anything); change to the state qtest. 4. On state qtest: • If the symbol read from the input-tape is the blank symbol and the symbol read from the work-tape is the start symbol B then write 1 on the output tape and change state to qhalt. • Otherwise, if the symbols read from the input tape and the work tape are not the same then write 0 on the output tape and change state to qhalt. Web draft 2007-01-08 21:59
1.2.MODELING COMPUTATION AND EFFICIENCY p1.9(19) Otherwise,if the symbols read from the input tape and the work tape are the same, then move the input-tape head to the right and the work-tape head to the left;stay in the state qtest. As you can see,fully specifying a Turing machine is somewhat tedious and not always very informative.While it is useful to work out one or two examples for yourself(see Exercise 4),in the rest of the book we avoid such overly detailed descriptions and specify TM's in a more high level fashion. REMARK 1.7 Some texts use as their computational model single tape Turing machines,that have one read/write tape that serves as input,work and output tape.This choice does not make any difference for most of this book's results (see Exercise 10).However,Example 1.6 is one exception:it can be shown that such machines require (n2)steps to compute the function PAL. 1.2.2 Robustness of our definition. Most of the specific details of our definition of Turing machines are quite arbitrary.For example, the following simple claims show that restricting the alphabet I to be f0,1,,,restricting the machine to have a single work tape,or allowing the tapes to be infinite in both directions will not have a significant effect on the time to compute functions:(Below we provide only proof sketches for these claims;completing these sketches into full proofs is a very good way to gain intuition on Turing machines,see Exercises 5,6 and 7.) CLAIM 1.8 For every f {0,1*10,1}and time-constructible T:N-N,if f is computable in time T(n) by a TM M using alphabet I then it is computable in time 4log TT(n)by a TM M using the alphabet{0,l,□，>}. M's tape::m a ch i n e■■■■■ 8 'stape:oio6 oo01000☐℃ Figure 1.3:We can simulate a machine M using the alphabet{D,☐，a,b,.,z}by a machine M'using{>,□，0，l} via encoding every tape cell of M using 5 cells of M'. PROOF SKETCH:Let M be a TM with alphabet T,k tapes,and state set Q that computes the function f in T(n)time.We will show a TM M computing f with alphabet {0,1,,,k tapes and a set Q'of states which will be described below.The idea behind the proof is simple:one can encode any member of I using log bits.3 Thus,each of M's work tapes will simply encode one 3Recall our conventions that log is taken to base 2,and non-integer numbers are rounded up when necessary. Web draft2007-01-0821:59
DRAFT 1.2. MODELING COMPUTATION AND EFFICIENCY p1.9 (19) • Otherwise, if the symbols read from the input tape and the work tape are the same, then move the input-tape head to the right and the work-tape head to the left; stay in the state qtest. As you can see, fully specifying a Turing machine is somewhat tedious and not always very informative. While it is useful to work out one or two examples for yourself (see Exercise 4), in the rest of the book we avoid such overly detailed descriptions and specify TM’s in a more high level fashion. Remark 1.7 Some texts use as their computational model single tape Turing machines, that have one read/write tape that serves as input, work and output tape. This choice does not make any difference for most of this book’s results (see Exercise 10). However, Example 1.6 is one exception: it can be shown that such machines require Ω(n 2 ) steps to compute the function PAL. 1.2.2 Robustness of our definition. Most of the specific details of our definition of Turing machines are quite arbitrary. For example, the following simple claims show that restricting the alphabet Γ to be {0, 1, , B}, restricting the machine to have a single work tape, or allowing the tapes to be infinite in both directions will not have a significant effect on the time to compute functions: (Below we provide only proof sketches for these claims; completing these sketches into full proofs is a very good way to gain intuition on Turing machines, see Exercises 5, 6 and 7.) Claim 1.8 For every f : {0, 1} ∗ → {0, 1} and time-constructible T : N → N, if f is computable in time T(n) by a TM M using alphabet Γ then it is computable in time 4 log |Γ|T(n) by a TM M˜ using the alphabet {0, 1, , B}. M’s tape: > m a c h i n e ~M’s tape: > 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 Figure 1.3: We can simulate a machine M using the alphabet {B, , a, b, . . . , z} by a machine M0 using {B, , 0, 1} via encoding every tape cell of M using 5 cells of M0 . Proof Sketch: Let M be a TM with alphabet Γ, k tapes, and state set Q that computes the function f in T(n) time. We will show a TM M˜ computing f with alphabet {0, 1, , B}, k tapes and a set Q0 of states which will be described below. The idea behind the proof is simple: one can encode any member of Γ using log |Γ| bits.3 Thus, each of M˜ ’s work tapes will simply encode one 3Recall our conventions that log is taken to base 2, and non-integer numbers are rounded up when necessary. Web draft 2007-01-08 21:59