The transition function ' 𝛿 ' in multi-tape Turing machine is defined as:
2022
The transition function ' 𝛿 ' 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}}\)
Attempted by 47 students.
Show answer & explanation
Correct answer: C
Correct transition function: For a deterministic k-tape Turing machine the transition function is δ: Q × Γ^k → Q × Γ^k × {L,R,S}^k.
Explanation:
Domain: one current state (an element of Q) and one symbol from each of the k tapes (Γ^k).
Codomain: one next state (an element of Q), k symbols to write (Γ^k), and k head moves ({L,R,S}^k).
Nondeterministic variant: the transition can return a set of possible moves, written as δ: Q × Γ^k → P(Q × Γ^k × {L,R,S}^k).
Why other forms are incorrect:
Any expression that places a power set or 2^Q in the domain is wrong because the input must be a single state, not a subset of states.
Expressions that include extra Q factors (for example an extra state factor in the domain or codomain) are incorrect because the transition describes one current state and one next state, not two states simultaneously.
Pay attention to notation: a correct formulation uses Γ^k (the k-fold Cartesian product of the tape alphabet) rather than a typographical variant like 'Γ k' without the superscript.
Final answer: δ: Q × Γ^k → Q × Γ^k × {L,R,S}^k (deterministic).
A video solution is available for this question — log in and enroll to watch it.