Formal Definition - Turing Machine

 

📘 Formal Definition - Turing Machine

A Turing Machine is a nine-tuple

M=(Q,Σ,Γ,δ,B,,s,t,r)M = (Q, \Sigma, \Gamma, \delta, s_0, B, ⊢, s_{acc}, s_{rej})

where:

  1. Q – a finite set of states
    (typically denoted r,s,t,...).

  2. Σ – the input alphabet,
    which does not contain the blank symbol B or the left-end marker .

  3. Γ – the tape alphabet, satisfying

    ΣΓ,BΓ,ΓΣ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ

    Every cell of the tape contains one symbol from Γ.

  4. δ – the transition function

    δ:(Q{t,r})×ΓQ×Γ×{L,R}δ : (Q - \{s_{acc}, s_{rej}\}) \times Γ \to Q \times Γ \times \{L, R\}

    Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state.

  5. s ∈ Q – the initial (start) state.

  6. B ∈ Γ – the blank symbol, representing the empty tape cell.

  7. ⊢ ∈ Γ – the left-end marker, which appears at the extreme left of the tape and is never overwritten.

  8. t ∈ Q – the accepting  state.

  9. r ∈ Q – the rejecting  state, with trs_{acc} \neq s_{rej}


🧠 Informal Behavior

  • The tape is infinite to the right and begins with on the leftmost cell.

  • The input string xΣx ∈ Σ^* is written immediately to the right of ⊢.

  • All remaining cells are filled with blanks (B).

  • The head starts on the first input symbol (just right of ⊢) in the start state s.

  • The machine repeatedly applies δ until it enters t or r, at which point it halts.




Transition function

δ:(Q{t
,r
})×ΓQ×Γ×{L,R}
\delta : (Q - \{ s_{acc}, s_{rej} \}) \times \Gamma \to Q \times \Gamma \times \{L, R\}

is defined as follows.

For each pair (p,a)(p, a) where
pQ{t
,r}
p \in Q - \{s_{acc}, s_{rej}\}
 and aΓa \in \Gamma,

δ(p,a)=(q,b,D)\boxed{ \delta(p, a) = (q, b, D) }

where:

  • qQq \in Q is the next state the machine enters,

  • bΓb \in \Gamma is the symbol written in the current tape cell (possibly replacing aa), and

  • D{L,R}D \in \{L, R\} indicates the direction of head movement

    • LL = move one cell to the left

    • RR = move one cell to the right


🧠 Intuitive Explanation

If the machine is in state pp and the tape head is scanning the symbol aa,
then δ(p,a)=(q,b,D)\delta(p, a) = (q, b, D) means:

  1. Replace the symbol aa on the tape with bb,

  2. Move the head one cell in direction DD (either left or right),

  3. Enter the new state qq.


⚠️ Special Conventions (Kozen’s Model)

  • The left-end marker (⊢) is never overwritten, i.e.,
    if a=a = ⊢, then b=b = ⊢ and D=RD = R.
    This ensures the head never moves left of the tape’s beginning.

  • The blank symbol (B) represents an empty cell, and blanks extend infinitely to the right.

  • The function δ is undefined for t
    s_{acc}
    and r— because the machine halts when it reaches either of these states.


🧩 Example

Suppose

δ(s0,a)=(s1,X,R)\delta(s_0, a) = (s_1, X, R)

This means:

  • When in state s0s_0 scanning symbol a,

  • write X on the tape,

  • move the head one cell to the right,

  • and change to state s₁.

Similarly,

δ(s1,b)=(s2,Y,L)\delta(s_1, b) = (s_2, Y, L)

means:

  • When in state s₁ scanning b,

  • write Y, move left, and go to state s₂

Comments

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Non deterministic Finite Automata NFA