Which of the following is the correct representation of a standard deterministic Turing Machine transition function?

Options

  • A. δ : Q × Γ → Q × Γ × {L, R}
  • B. δ : Q → Γ
  • C. δ : Γ → Q
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. δ : Q × Γ → Q × Γ × {L, R}

Detailed Explanation

  • Q: Set of states.
  • Γ: Tape alphabet.
  • δ: Transition function.
  • Output: Next state, symbol to write and head movement.
  • Note: Some formal definitions also include a stationary head movement S.