Turing Machines

Deterministic Turing Machines

• Transition Function: Key aspect of Turing machines. Describes state transitions based on current state, tape symbol.

Definition 15 (Turing Machine)

A Turing machine is defined as a 7-tuple ((Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})) where:

1. Q: Finite set of states.
2. Σ: Finite input alphabet, excluding the blank symbol.
3. Γ: Finite tape alphabet, includes blank symbol (\sqcup) and input alphabet (Σ).
4. δ: Transition function.
5. q₀: Start state.
6. qₐccept: Accept state.
7. qₑject: Reject state, distinct from accept state.

Computation of a Turing Machine

• Configuration: Defined by the current state, tape contents, and head location.
  • Notation: (ua, q_i, bv) represents a configuration.
• Yields:
  • Left Move: (ua, q_i, bv \text{ yields } u, q_j , acv)
  • Right Move: (ua, q_i, bv \text{ yields } uac, q_j , v)
• Special Cases:
  • At leftmost position: Transition differs based on direction.
• Start Configuration: (q₀, w) where (w) is the input.
• Accepting Configuration: State is (q_{accept}).
• Rejecting Configuration: State is (q_{reject}).

Non-deterministic Turing Machines

• Similar to deterministic but can branch into multiple states.

Definition 16 (Non-deterministic Turing Machine)

A non-deterministic Turing machine is also a 7-tuple similar to deterministic ones, but the transition function differs.

Key Theorem

• Theorem 14: Every non-deterministic Turing machine has an equivalent deterministic Turing machine.
  • Proof reference: Theorem 3.16 in "Introduction to the Theory of Computation" by Michael Sipser.