Skip to content

AEiE0803 Turing machine

Turing-machine fundamentals

  • A Turing machine (TM) is the standard abstract model of general computation.
  • It has a finite control, an infinite tape, and a read-write head.
  • A TM may accept, reject, or run forever.
  • A language \(L\) is recursively enumerable or Turing-recognizable if some TM accepts exactly the strings in \(L\); on nonmembers it may reject or loop forever.
  • A language is decidable if some TM halts on every input and accepts exactly the strings in the language.

Typical tuple form:

\[ M=(Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej}) \]

Typical transition notation:

\[ \delta(q,a)=(p,b,R) \]

meaning read \(a\), write \(b\), move right, and enter state \(p\).

Roles and variants

Role or variant Meaning Recognition cue
Recognizer Accepts language members May loop on nonmembers
Decider Always halts Accept or reject for every input
Computing function Produces output on tape Input-output viewpoint
Enumerator Prints language strings Generates members one by one
Multi-track TM Several tracks in one tape cell Same power as standard TM
Multi-tape TM Several tapes and heads Same power, often faster
Nondeterministic TM Branching computation Same decidable and RE classes
Universal TM Simulates encoded TMs Stored-program idea
  • These variants improve convenience or efficiency, not computability class.
  • The universal TM reads an encoding \(\langle M,w \rangle\) and simulates machine \(M\) on input \(w\).

Church-Turing thesis, acceptance, and complexity

  • Church-Turing thesis is a thesis, not a proved theorem.
  • It states that any effectively computable procedure can be performed by a TM.
  • A string is accepted if the machine enters an accept state.
  • A recognizer may loop forever on a nonmember.
  • Time complexity counts transition steps as a function of input length \(n\).
  • Space complexity counts the number of tape cells used.

Decidability limits

  • Some problems are undecidable: no TM decides them for all inputs.
  • The Halting Problem is the standard undecidable problem.
  • Recursively enumerable is weaker than decidable.
  • Reducibility is used to transfer undecidability from a known hard problem.

Recognition cues for Turing machines

  • "Always halts" indicates decider, not mere recognizer.
  • "Can enumerate all strings in the language" refers to an enumerator.
  • "Simulates every TM" points to universal TM.
  • "Undecidable" means no algorithm exists for every instance, not just that the problem is difficult.

Common traps in Turing machines

  • Nondeterminism does not add computability power to TMs.
  • Multi-track and multi-tape TMs are equivalent in computational power to the standard TM.
  • Church-Turing thesis cannot be proved purely mathematically because it links a formal notion to an informal one.
  • A recognizer is not automatically a decider.

One-step examples for Turing machines

  • A TM for \(\{0^n1^n\}\) can repeatedly mark one 0 and one 1 until nothing unmatched remains.
  • An enumerator for all binary strings may output \(\varepsilon,0,1,00,01,10,11,\ldots\) in length-lexicographic order.
  • A universal TM is the abstraction behind an interpreter that runs many different programs given as data.

Turing-machine revision box

TM is the baseline model of general computation. Recognizer may loop; decider must halt. Multi-tape, multi-track, and nondeterministic TMs do not exceed the ordinary TM in computability power. Halting is the canonical undecidable problem.