Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Turing machines

Clear, exam-focused notes on Turing machines: definitions, formalism, design techniques, key theorems (undecidability of A_TM), worked constructions and traces, common mistakes, and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Turing machines formalize the idea of computation. Engineers use these concepts when reasoning about what problems can or cannot be solved by programs, proving limits of algorithms, and understanding complexity classes and reductions used in later topics such as Decidability, Reducibility, P vs NP and Variants of Turing machines.

Key ideas

  • Σ is the input alphabet (does not contain the blank symbol).

  • Γ is the tape alphabet, with Σ ⊂ Γ and a special blank symbol ⊔ in Γ \ Σ.

  • δ : (Q \ {q_accept, q_reject}) × Γ → Q × Γ × {L, R} is the (deterministic) transition function.

  • q0 ∈ Q is the start state.

  • q_accept, q_reject ∈ Q, distinct final states. When machine enters either, it halts. Define each term as it first appears above.

  • Configuration: a complete instantaneous description of TM: a string of the form u q a v meaning the tape contains u a v, head is on symbol a, and current state is q. The rest of tape is blank. Draw configuration as a tape with cells, label the head position and current state above that cell.

  • Acceptance and rejection: M accepts input w if starting from initial configuration (q0, tape containing w with blanks around), M eventually enters q_accept. M rejects if it enters q_reject.

  • Halting: a TM halts on input if it reaches either q_accept or q_reject. If it never reaches either, it runs forever.

  • Decidable (Turing-decidable, recursive) language: a language L is decidable if there exists a TM M that halts on every input and accepts exactly the strings in L.

  • Turing-recognizable (recursively enumerable) language: L is Turing-recognizable if there exists a TM that accepts every w ∈ L, and either rejects or loops forever on w ∉ L. (Often called recogniser.) A language is decidable iff both it and its complement are Turing-recognizable (co-recognizable). Recognizable languages are closed under union and intersection; decidable languages are closed under union, intersection, and complement.

  • Nondeterministic Turing machine (NDTM): same as TM but δ is a relation giving multiple possible moves; the machine accepts if any computational branch accepts. Important theorem: every NDTM has an equivalent deterministic TM (computational power equal); only time may differ.

  • Universal Turing machine (UTM): a TM U that takes as input an encoding ⟨M⟩ of a TM M and an encoding of input w, and simulates M on w. Existence shows TMs can interpret programs.

  • Church–Turing thesis (informal): any effectively computable function (intuitively computable by an algorithm) is computable by a Turing machine. This is not a formal theorem but an accepted thesis.

  • Key undecidability result (informal exact statement): A_TM = {⟨M, w⟩ | M is a TM and M accepts w} is undecidable. Proof idea: assume a decider R for A_TM exists, build machine S that on input ⟨M⟩ runs R(⟨M,⟨M⟩⟩) and flips the answer; run S on ⟨S⟩ to get contradiction. This is diagonalization / self-reference. Note: A_TM is Turing-recognizable by simulating M on w and accepting if M accepts.

  • Halting problem HALT = {⟨M, w⟩ | M halts on w} is undecidable, but HALT is Turing-recognizable: simulate M on w and accept if it halts. Its complement is not Turing-recognizable (otherwise HALT would be decidable).

  • Variants with same power: multitape TMs, nondeterministic TMs, and TMs with larger alphabets are equivalent in language recognition; show simulation constructions and mention possible polynomial time overhead for multitape-to-single-tape.

  • What to draw in proofs: when simulating machines, draw a two-track tape picture or multiple tapes; when showing undecidability, draw a flow: assume decider → construct S → contradiction by running S on ⟨S⟩.

Formulas

M = (Q, Σ, Γ, δ, q0, q_accept, q_reject) — M: Turing machine tuple; Q: finite states; Σ: input alphabet; Γ: tape alphabet; δ: transition function; q0: start state; q_accept/q_reject: halting states. (Applies to deterministic single-tape TM.)

δ : (Q \ {q_accept,q_reject}) × Γ → Q × Γ × {L,R} — transition function type. First component: current state and tape symbol; output: new state, symbol to write, and head move L/R.

conf = u q a v — configuration notation: tape left content u, current state q, head on symbol a, right content v.

A_TM = {⟨M,w⟩ | M is TM and M accepts w} — language of accepting pairs.

HALT = {⟨M,w⟩ | M halts on input w} — halting problem language.

(Units: not applicable; these are syntactic forms to remember.)

Worked examples

  1. Design a TM that decides L = { a^n b^n | n ≥ 0 }.

    • Idea: cross off one a and one b repeatedly. Alphabet Γ = {a, b, X, ⊔}, where X marks checked symbols.
    • States: q0 start, q_scan_right (find first b), q_check_left (return), q_accept, q_reject.
    • Informal δ steps:
      1. In q0: if read a, write X, move R, go to q_scan_right; if read X, move R stay q0; if read b (no a left), reject; if blank (all input processed), accept.
      2. In q_scan_right: move R skipping a and X until first b; if find b write X, move L, go to q_check_left; if blank before b, reject (unequal counts).
      3. In q_check_left: move L until you see X or blank; when you see X, move R and go to q0 to repeat; if you see a blank (left end), move R and go to q0.
    • Trace on input aabb (show configurations step-by-step):
      • Initial: q0 a a b b
      • After marking first a: X q_scan_right a b b → move to first b, mark it: X a X q_check_left b → move left to X, then return to q0 at next symbol.
      • Repeat marking second pair → eventually see blank in q0 and accept.
    • This TM halts on all inputs, so it decides L.
  2. Show A_TM is not decidable (model answer sketch expected in exams):

    • Claim: A_TM is undecidable.
    • Proof by contradiction: suppose R decides A_TM.
    • Construct machine S that on input ⟨M⟩ does: run R on ⟨M,⟨M⟩⟩. If R accepts, S rejects. If R rejects, S accepts. (S is computable using R.)
    • Consider S run on ⟨S⟩. If R says S accepts ⟨S⟩, then by S's definition S rejects ⟨S⟩ — contradiction. If R says S does not accept ⟨S⟩, S accepts ⟨S⟩ — contradiction. Therefore R cannot exist; A_TM undecidable.
    • Note: explain difference between 'accepts' and 'halts' carefully.
  3. Recognizer for HALT (short): To show HALT is Turing-recognizable, build machine U that on input ⟨M,w⟩ simulates M on w step-by-step; if simulation halts (accept or reject), U accepts. If M never halts, U never accepts. Thus HALT is RE.

Common mistakes

  • Writing transitions that move left at the leftmost cell without handling blanks — always allow ⊔ to the left.
  • Mixing up acceptance conditions for nondeterministic machines (accept if any branch accepts) vs deterministic.
  • In undecidability proofs, failing to construct the self-referential machine S correctly (must use the assumed decider as a subroutine).

For your exam

  • For definitions: exact tuple and explanation of each symbol.
  • For designs: clear alphabet and states, transition rules (or clear English description mapping to δ), and a short correctness argument and halting behavior.
  • For proofs: state assumptions clearly, give construction (e.g., S), and derive contradiction; describe where self-reference is used.
  • For trace: show each configuration until halting or until required number of steps.

Quick check

  1. Define a Turing-decidable language in one sentence.
  2. What is a configuration of a TM and how do you write it?
  3. Why is nondeterminism not more powerful than determinism for TMs (informal reason)?

Answers: 1) A language is Turing-decidable if a TM exists that halts on every input and accepts exactly strings in the language. 2) A configuration is an instantaneous description; written u q a v representing tape left part u, current state q at symbol a, and right part v. 3) Every nondeterministic TM can be simulated by a deterministic TM by interleaving (breadth-first) simulation of its branches or by encoding nondet choices on a single tape, so they accept the same languages (possibly with time overhead).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?