THREE EQUIVALENT NOTATIONS, chosen by convenience. ── 1. THE FORMAL 7-TUPLE ─────────────────────────────────── M = (Q, Σ, Γ, δ, q₀, B, F) Used when the machine must be reasoned about rather than executed. It is the notation for proofs. ── 2. THE TRANSITION TABLE ───────────────────────────────── Rows are states, columns are tape symbols, and each entry gives the triple (next state, symbol written, direction). FOR THE aⁿbⁿ MACHINE OF THE LAST TOPIC: STATE │ a │ b │ X │ Y │ B ──────┼───────────┼───────────┼───────────┼───────────┼────── q₀ │ (q₁,X,R) │ — │ — │ (q₃,Y,R) │ ACC q₁ │ (q₁,a,R) │ (q₂,Y,L) │ — │ (q₁,Y,R) │ — q₂ │ (q₂,a,L) │ — │ (q₀,X,R) │ (q₂,Y,L) │ — q₃ │ — │ — │ — │ (q₃,Y,R) │ ACC A DASH MEANS NO TRANSITION IS DEFINED, and the machine HALTS AND REJECTS. This is how a table encodes rejection without a separate reject state. NOTE THAT THE TABLE IS EXACTLY THE FUNCTION δ WRITTEN OUT, and reading it row by row is how one executes the machine by hand. ── 3. THE TRANSITION DIAGRAM ─────────────────────────────── States as circles, transitions as arrows labelled X / Y , D meaning "reading X, write Y, move D". A self-loop labelled a/a,R means "skip over a's, moving right" — the commonest idiom in Turing machine diagrams. DIAGRAMS ARE READABLE FOR SMALL MACHINES AND USELESS FOR LARGE ONES, which is why serious constructions are given as tables or as high-level descriptions. ── 4. HIGH-LEVEL DESCRIPTION ─────────────────────────────── In practice, and in most examinations beyond the elementary level, machines are described in structured English: "On input w: 1. Scan right to find the first unmarked a; if none, go to step 4. 2. Mark it X and scan right for the first unmarked b. If none is found, REJECT. 3. Mark it Y, return to the leftmost X, and repeat from step 1. 4. Scan right; if only Y's and then a blank remain, ACCEPT, otherwise REJECT." THIS IS LEGITIMATE AND STANDARD. By the Church-Turing thesis, any such description can be turned into a formal machine, and writing out the states adds no insight. THE SKILL BEING EXAMINED IS USUALLY THE ALGORITHM, NOT THE BOOKKEEPING — though a question that explicitly asks for a transition table expects one. ── THE THREE LEVELS OF DESCRIPTION, named ────────────────── FORMAL — the 7-tuple or full transition table IMPLEMENTATION — prose describing head movements and tape contents, without listing states HIGH-LEVEL — prose describing the algorithm, ignoring the tape entirely ALL THREE ARE ACCEPTED IN PROOFS. Choosing the highest level that still makes the argument clear is a mark of a good answer.

── THE INSTANTANEOUS DESCRIPTION (ID) ────────────────────── A single string capturing the ENTIRE state of the machine: α q β · α is the tape content strictly LEFT of the head · q is the current state · β is the tape content FROM the head rightward · THE HEAD IS ON THE FIRST SYMBOL OF β · Infinite blanks beyond the written portion are omitted EXAMPLES on the aⁿbⁿ machine: q₀ aabb start: head on the first a X q₁ abb one a marked, head on the second X q₂ aYb returning leftward XXYY q₃ all marked, head at the trailing blank WHY THE HEAD POSITION IS ENCODED BY THE POSITION OF q IN THE STRING: this makes an ID a plain string over Γ ∪ Q, which is essential later — the universal Turing machine must READ IDs as data, and a string is the only thing a tape can hold. ── THE MOVE RELATION ─────────────────────────────────────── Write ID₁ ⊢ ID₂ for "one step", and ⊢* for "zero or more". FOR A RIGHT MOVE, δ(q, X) = (p, Y, R): α q X β ⊢ α Y p β the head symbol X becomes Y, and q moves rightward past it. FOR A LEFT MOVE, δ(q, X) = (p, Y, L), with Z the symbol immediately left of the head: α Z q X β ⊢ α p Z Y β q moves leftward past Z, and X has become Y. THE LEFT-MOVE CASE IS THE ONE STUDENTS GET WRONG — note that the symbol WRITTEN (Y) stays where it was, while the STATE marker jumps to the left of Z. ── A COMPUTATION AS A SEQUENCE OF IDs ────────────────────── The full run on aabb, written as IDs: q₀aabb ⊢ Xq₁abb ⊢ Xaq₁bb ⊢ Xq₂aYb ⊢ q₂XaYb ⊢ Xq₀aYb ⊢ XXq₁Yb ⊢ XXYq₁b ⊢ XXq₂YY ⊢ Xq₂XYY ⊢ XXq₀YY ⊢ XXYq₃Y ⊢ XXYYq₃ THIRTEEN IDs — one more than the twelve moves, since the first ID is the starting configuration. THE FINAL ID HAS q₃ AT THE END WITH THE HEAD ON A BLANK, which is the accepting condition for this machine. NOTE WHAT AN ID SEQUENCE IS: A COMPLETE, VERIFIABLE RECORD OF A COMPUTATION. Each step can be checked against δ independently of every other step, which is precisely the property that makes the later reduction proofs work — a computation history can be treated as a string and reasoned about with grammars. ── ACCEPTANCE STATED IN ID NOTATION ──────────────────────── L(M) = { w ∈ Σ* : q₀w ⊢* α p β for some p ∈ F } and three possible outcomes on any input: ACCEPT — an accepting state is reached REJECT — the machine halts with no applicable transition and is not in an accepting state LOOP — the machine never halts THE THIRD OUTCOME IS WHAT DISTINGUISHES THIS MODEL FROM EVERYTHING EARLIER, and the notation must be able to express it: an infinite sequence of IDs with no final one. ── CONVENTIONS THAT VARY BETWEEN TEXTBOOKS ───────────────── Worth knowing, since an exam may use any of them: · TAPE INFINITE IN ONE DIRECTION (the usual convention) or BOTH. Equivalent — a two-way tape is simulated by folding it onto two tracks of a one-way tape. · HALTING STATES: some treatments use explicit q_accept and q_reject states and require the machine to halt only in those; others let an undefined transition mean rejection, as above. · A STAY-PUT direction S in addition to L and R. Adds no power: replace each S move with a move right followed by a move left. · THE INPUT'S POSITION: normally the head starts on the leftmost input symbol, with blanks everywhere else. STATE YOUR CONVENTION AT THE START OF AN ANSWER. Examiners accept any consistent one; they do not accept a machine whose behaviour depends on which convention the reader assumes.