randomization included is O(nlogn). However, since by the tiniest of chances each of the pivot choices could take the largest or smallest element, the worst-case running time of Quicksort is still O(n). Nevertheless, Quicksort is still the method of choice in many applications (it is used in the UNIX sort command, for example), since its expected running time is really quite good compared with other approaches, even with methods that are 0{n log n) in the worst case.

11.4.2 A Turing-Machine Model Using Randomization

To represent abstractly the ability of a Turing machine to make random choices, much like a program that calls a random-number generator one or more times, we shall use the variant of a multitape TM suggested in Fig. 11.6. The first tape holds the input, as is conventional for a multitape TM. The second tape also begins with nonblanks in its cells. In fact, in principle, its entire tape is covered with Os and Is, each chosen randomly and independently with probability 1/2 of a 0 and the same probability of a 1. We shall refer to the second tape as the random tape. The third and subsequent tapes, if used, are initially blank and are used as scratch tapes by the TM if needed. We call this TM model a randomized Turing machine.

Randombits ... 00101000101001000010091111

Scratch tape(s)

Figure 11.6: A Turing machine with the capability of using randomly generated numbers

Since it may not be realistic to imagine that we initialize the randomized TM by covering an infinite tape with random Os and Is, an equivalent view of this TM is that the second tape is initially blank. However, when the second head is scanning a blank, an internal coin flip occurs, and the randomized

TM immediately writes either a 0 or a 1 on the tape cell scanned and leaves it there forever without change. In that way, there is no work - certainly not infinite work - done prior to starting the randomized TM. Yet the second tape appears to bo covered with random Os and Is, since those random bits appear wherever the randomized TMs second tape head actually looks.

Example 11.12: We can implement the randomized version of Quicksort on a randomized TM. The important step is the recursive process of taking a sublist, which we assume is stored consecutively on the input tape and delineated by markers at both ends, picking a pivot at random, and dividing the sublist into low and high sub-sublists. The randomized TM does as follows:

1. Suppose the sublist to be divided is of length m. Use about О (logm) new random bits on the second list to pick a random number between 1 and m; the mth element of the sublist becomes the pivot. Note that we may not be able to choose every integer between 1 and m with absolutely equal probability, since m not be a power of 2. However, if we take, say [2 log2 ml bits from tape 2, think of it as a number in the range 0 to about m, take its remainder when divided by m, and add 1, then we shall get all numbers between 1 and m with probability that is close enough to 1/m to make Quicksort work properly.

2. Put the pivot on tape 3.

3. Scan the sublist delhieated on tape 1, copying those that are no greater than the pivot to tape 4.

4. Again scan the sublist on tape 1, copying those elements greater than the pivot to tape 5.

5. Copy tape 4 and then tape 5 to the space on tape 1 that formerly held the delineated sublist. Place a marker between the two lists,

6. If either or both of the sub-sublists have more than one element, recursively sort them by the same algorithm.

Notice that this implementation of Quicksort takes 0{n logn) time, even though the computing device is a multitape TM, rather than a conventional computer. However, the point of this example is not the running time but rather the use of the random bits on the second tape to cause random behavior of the Turing machine. □

11.4.3 The Language of a Randomized Turing Machine

We are used to a situation where every Turing machine (or FA or PDA for that matter) accepts some language, even if that language is the empty set or the set of all strings over the input alphabet. When we deal with randomized Turing machines, we need to be more careful about what it means for the TM

to accept an input, and it becomes possible that a randomized TM accepts no language at all. The problem is that when we consider what a randomized TM M does in response to an input w, we need to consider M with all possible contents for the random tape. It is entirely possible that M accepts with some random strings and rejects with others; in fact, if the randomized TM is to do anything more efficiently than a deterministic TM, it is essential that different contents of the randomized tape lead to different behaviors.

К we think of a randomized TM as accepting by entering a final state, as for a conventional TM, then each input w to the randomized TM M has some probability of acceptance, which is the fraction of the possible contents of the random tape that lead to acceptance. Since there are an infinite number of possible tape contents, we have to be somewhat careful computing this proba-bihty. However, any sequence of moves leading to acceptance looks at only a finite portion of the random tape, so whatever is seen there occurs with a finite probability equal to 2 * if m is the number of cells of the random tape that have been scanned and influenced at least one move of the TM. An example will illustrate the calculation in a very simple case.

Example 11.13 : Our randomized TM M has the transition function displayed m Fig. 11.7. M uses only an input tape and the random tape. It behaves in a very simple manner, never changing a symbol on either tape, and moving its heads only to the right (direction R) or keeping them stationary (direction S). Although we have not defined a formal notation for the transitions of a randomized TM, the entries in Fig. 11.7 should be understandable; each row-corresponds to a state, and each column corresponds to a pair of symbols XY, where X is the symbol scanned on the input tape, and У is the symbol scanned on the random tape. The entry in the table gUVDE means that the TM enters state g, writes U on the Input tape, writes V on the random tape, moves the input head in direction D, and moves the head of the random tape ш duection

Figure 11.7: The transition function of a randomized Turing machine

You should be aware that the randomized TM described in Example 11.12 Is not a language-recognizing TM. Rather, it performs a transformation on its input, and the running time of the transformation, although not the outcome, depends on what was on the random tape.