Random TM
KR Chowdhary
Professor & Head
Email: kr.chowdhary@gmail.com
Department of Computer Science and Engineering
MBM Engineering College, Jodhpur

kr chowdhary

Random TM

1/ 4

TM Model Using Randomization

Standard TM is deterministic, and for every state, tape symbol pair there
is definite transition. The idea of random TM comes from random
numbers theory/probability theory for solution of problems. For example,
forecasting results, or accidents, or failure rates, Monte-Carlo method for
integration, death and birth rates, are some of the problems solved using
random/probability theory. This idea was an inspiration for random TM.
The structure of Random TM is as follows:
- tape 1 holds input w.
- Tape 2 has random 0s and 1s. (called random tape)
- Tape 3 and subsequent tapes (if used) are initially blank and used as
scratch pads.
- For random bits an internal coin flips and writes 0 or 1 (to always generate
a random number before it is needed. thus, tape 2, is assumed to
comprise infinite random numbers: 0,1 sequences).

kr chowdhary

Random TM

2/ 4

Randomized version of quick sort

In quick sort, a pivot needs to be decided at random position out of the list
to be sorted, and this list is split into two; those elements that are ≤ the
pivot and those which are greater that pivot. The same process is applied
recursively on each list and so on. The algorithm for TM is as follows:
Pick a pivot at random and divide sublists into left and right
If sublist to be divided is |w | = m, O(n log n) bits are required to pick a
random number 1 to m.
put pivot on tape 3, scan sublist on tape1, copy the number no-greater to
tape 4, and greater to tape 5.
Copy tape 4, 5 back to tape 1.
If either sublist is of length greater than 1, recursively solve it.
The complexity for solution is O(n log n ), and complexity class is RP
(Randomized polynomial class).
If pivot always divides elements into sub-lists of 1 and n-1, it is insertion
sort, with complexity O(n2 ). But, random selection of pivot postion gives
average case complexity of O(n log n)

kr chowdhary

Random TM

3/ 4

Classes on randomized machine

Class RP: (randomized polynomial)
- These are set of languages L recognized in Randomized Polynomial time
on Randomized TM M.
- If w ∈
/ L, then probability that M accepts w is 0.
- If w ∈ L, then probability that M accepts w is at least ½.
- If |w | = n, RTM halts after T (n) steps.
Class ZAPP: ( Zero error, Probabilistic, polynomial)
- It is class based on randomized TM that always halts.
- Time is polynomial of length of Input.
- Expected run time instead of worst case running time is used for
complexity.
Class BPP: (Bounded error probabilistic polynomial time class
- Solvable by probabilistic TM in P time, with error probability 1/3 of all
instances.

kr chowdhary

Random TM

4/ 4