Let k0 be an integer. A k-tape offline Turing machine has k+1 doubly infinite tapes numbered from 0 to k. Tape 0 is also called the input tape. Each tape has has a head. At any moment, head i (i=0,...,k) scans a tape cell in tape i. All tape cells contains the blank symbol initially, except for the input word stored in tape 0. Initially, head 0 scans the first symbol of the input word, and the state is q0 (start state). There after, the machine makes transitions that corresponds to executing some instruction from a finite set called the transition table.