UGCNET CSE December 2022: 29

Question

 

The transition function ' $\delta$ ' in multi-tape Turing machine is defined as:

• A. $\delta: 2 \mathrm{Q} \times \Gamma^{\mathrm{k}} \rightarrow 2^{\mathrm{Q}} \times \Gamma^{\mathrm{k}} \times\{\mathrm{L}, \mathrm{R}, \mathrm{S}\}^{\mathrm{k}}$
• B. $\delta: \mathrm{Q} \times \mathrm{Q} \times \Gamma^{\mathrm{k}} \rightarrow \mathrm{Q} \times \mathrm{Q} \times \Gamma^{\mathrm{k}} \times\{\mathrm{L}, \mathrm{R}, \mathrm{S}\}^{\mathrm{k}}$
• C. $\delta: \mathrm{Q} \times \Gamma \mathrm{k} \rightarrow \mathrm{Q} \times \Gamma^{\mathrm{k}} \times\{\mathrm{L}, \mathrm{R}, \mathrm{S}\}^{\mathrm{k}}$
• D. $\delta: \mathrm{Q} \times \Gamma^{\mathrm{k}} \times 2^{\mathrm{Q}} \rightarrow \mathrm{Q} \times \Gamma^{\mathrm{k}} \times 2^{\mathrm{Q}} \times\{\mathrm{L}, \mathrm{R}, \mathrm{S}\}^{\mathrm{k}}$

(Option $1 [39413]) 1$
(Option $2[39414]) 2$
(Option $3[39415]) 3$
(Option $4 [39416]) 4$

Answer Given by Candidate : $3$

Answer 1

From a state $Q$, we can take $\Gamma^k$ combinations of inputs from $k$ tapes and move to a $Q$ state, replacing the tape contents from $\Gamma^k$ combinations and moving in $\{L, R, S\}$ directions in $k$ tapes.