📘 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: Q – a finite set of states (typically denoted r , s , t , ... ). Σ – the input alphabet , which does not contain the blank symbol B or the left-end marker ⊢ . Γ – the tape alphabet , satisfying Σ ⊆ Γ , B ∈ Γ , ⊢ ∈ Γ Σ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ Every cell of the tape contains one symbol from Γ. δ – 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. s ∈ Q – the initial (start) state . B ∈ Γ – the blank symbol , representing the empty tape cell. ⊢ ∈ Γ – the left-end marker , which appears at the extreme left of the tape and is never overwritte...
Comments
Post a Comment