TM as a Language Recognizer

Theory of Computation & Computer Graphics — Turing Machine, NEC licence examination syllabus (Nepal Engineering Council).

TM as a Language Recognizer

The role that places Turing machines at the top of the Chomsky hierarchy.

🌍 Where this lives: Every type checker is a language recogniser in this sense. When a compiler decides whether a program is well-typed, it is deciding membership in the language of well-typed programs — and for some languages that decision is genuinely hard. C++ template instantiation is Turing-complete, which means the compiler can be made to run an arbitrary computation at compile time, and in principle to never terminate. Compilers impose an arbitrary recursion depth limit precisely because the underlying problem is undecidable. Search "C++ templates Turing complete compile time computation".

Recognising languages beyond context-free

A TURING MACHINE RECOGNISES A LANGUAGE BY ACCEPTING EXACTLY ITS MEMBERS. What makes this significant is HOW MUCH MORE it can recognise than the earlier models. ── THE MOTIVATING EXAMPLE: aⁿbⁿcⁿ ────────────────────────── Proved NOT context-free by the pumping lemma. A Turing machine handles it easily. HIGH-LEVEL DESCRIPTION: "On input w: 1. Scan the tape to check the form a*b*c* — if the symbols are out of order, REJECT. 2. Return to the left end. 3. Repeat: cross off one a, one b and one c. If any runs out before the others, REJECT. 4. When all are crossed off, ACCEPT." THE MECHANISM IS THE SAME "COUNTING BY PAIRING" AS FOR aⁿbⁿ, EXTENDED TO A TRIPLE. And that is exactly what a PDA could not do: a stack matches ONE pair because it is consumed while being read, whereas the TAPE CAN BE TRAVERSED AGAIN AND AGAIN, so any number of counts can be compared. NOTE THE COST. Each pass crosses off one of each symbol and requires walking the whole tape, so the machine takes O(n) passes of O(n) steps each — Θ(n²) TIME. A more careful machine can do better, but the point stands: THE TM PAYS IN TIME FOR WHAT THE PDA COULD NOT DO AT ALL. ── MORE LANGUAGES A TM RECOGNISES ────────────────────────── { ww : w ∈ Σ* } — not context-free; the TM marks the midpoint and compares position by position { aⁿ : n is prime } — the TM performs trial division on the tape { aⁿ : n is a perfect square } { ⟨G⟩ : G is a graph with a Hamiltonian cycle } any language a computer program can decide THE GENERAL PRINCIPLE, and it is the practical statement of the Church-Turing thesis: IF YOU CAN DESCRIBE AN ALGORITHM THAT DECIDES MEMBERSHIP, A TURING MACHINE CAN CARRY IT OUT. ── THE STANDARD TECHNIQUES ───────────────────────────────── Turing machine constructions reuse a small number of idioms, and recognising them is most of the skill: 1. MARKING — overwrite symbols with marked versions (a → X) to record what has been processed. THE MOST-USED TECHNIQUE, and the basis of every counting machine. 2. SHUTTLING — sweep left and right repeatedly, doing a little work each pass. 3. COPYING — duplicate a portion of the tape elsewhere, using marks to track progress. 4. COMPARING — walk two marked regions in step, checking symbols match. 5. USING A DELIMITER — write a special symbol (#) to separate working regions. 6. MULTIPLE TRACKS — treat one tape as several parallel tapes by using composite symbols, which is the subject of a later topic. THESE COMPOSE. A machine for { ww } uses marking to find the midpoint, then comparing to check the halves — and a machine for multiplication uses copying inside a loop controlled by marking. ── LINEAR BOUNDED AUTOMATA AND TYPE 1 ────────────────────── A LINEAR BOUNDED AUTOMATON (LBA) is a Turing machine whose tape is RESTRICTED TO THE PORTION HOLDING THE INPUT (or a constant multiple of it). LBAs recognise exactly the CONTEXT-SENSITIVE LANGUAGES — Type 1 of the Chomsky hierarchy. THE SPACE RESTRICTION HAS A REMARKABLE CONSEQUENCE: an LBA has only FINITELY MANY POSSIBLE CONFIGURATIONS, since the tape length is bounded. Specifically, with |Q| states, |Γ| tape symbols and n cells, there are at most |Q| × n × |Γ|ⁿ configurations. IF THE MACHINE RUNS LONGER THAN THAT, IT MUST HAVE REPEATED A CONFIGURATION AND IS THEREFORE LOOPING. SO MEMBERSHIP FOR CONTEXT-SENSITIVE LANGUAGES IS DECIDABLE: run the LBA for that many steps and stop. THIS IS WHY CONTEXT-SENSITIVE ⊊ RECURSIVE — the bounded tape buys back the guarantee of termination that a general TM lacks. AND IT ILLUSTRATES THE GENERAL LESSON OF THE WHOLE SECTION: UNDECIDABILITY COMES FROM UNBOUNDEDNESS. Bound the space and everything becomes decidable, albeit expensively.

The hierarchy completed, and what lies beyond

── THE FULL PICTURE ──────────────────────────────────────── CLASS MACHINE GRAMMAR ──────────────────────────────────────────────────────── REGULAR finite automaton Type 3 CONTEXT FREE pushdown automaton Type 2 CONTEXT SENSITIVE LINEAR BOUNDED Type 1 AUTOMATON RECURSIVE TM THAT ALWAYS (no grammar (decidable) HALTS characterisation) RECURSIVELY Turing machine Type 0 ENUMERABLE NOT RE NO MACHINE AT ALL — ──────────────────────────────────────────────────────── THE SEPARATING LANGUAGES, each proved in its own topic: aⁿbⁿ regular → context free aⁿbⁿcⁿ context free → context sensitive the HALTING PROBLEM recursive → RE the COMPLEMENT of the halting problem RE → not RE NOTE THAT THE LAST CLASS IS NOT EMPTY. THERE ARE LANGUAGES NO MACHINE RECOGNISES AT ALL — not even one allowed to loop forever on non-members. The complement of the halting problem is the standard example, and its existence follows from the complementation theorem of the previous topic. ── A COUNTING ARGUMENT FOR WHY MOST LANGUAGES ARE NOT RE ─── A short and striking argument worth knowing: · EVERY TURING MACHINE CAN BE ENCODED AS A FINITE STRING, so there are COUNTABLY MANY Turing machines — the same cardinality as the natural numbers. · A LANGUAGE IS A SUBSET OF Σ*, and Σ* is countably infinite, so there are UNCOUNTABLY MANY languages — the cardinality of the power set of the naturals. · THEREFORE THERE ARE STRICTLY MORE LANGUAGES THAN MACHINES. SINCE EACH MACHINE RECOGNISES AT MOST ONE LANGUAGE, ALMOST ALL LANGUAGES ARE RECOGNISED BY NO MACHINE. THIS PROVES NON-RE LANGUAGES EXIST WITHOUT EXHIBITING ONE. It is a pure counting argument, and it says something startling: THE COMPUTABLE IS A VANISHINGLY SMALL FRAGMENT OF THE MATHEMATICALLY DESCRIBABLE. The languages we can compute are not merely a proper subset — they are a set of measure zero among all languages. ── UNIVERSALITY AND TURING COMPLETENESS ──────────────────── A system is TURING COMPLETE if it can simulate a Turing machine, and therefore compute anything computable. THE SURPRISING MEMBERS OF THIS CLUB: · every general-purpose programming language · C++ TEMPLATE INSTANTIATION · SQL with recursive common table expressions · CONWAY'S GAME OF LIFE · Minecraft redstone circuitry · the x86 MOV instruction alone · Magic: The Gathering, as a card game THE LESSON IS THAT TURING COMPLETENESS IS EASY TO ACHIEVE ACCIDENTALLY. A system needs only conditional branching and unbounded storage, and those appear in places nobody intended. THE PRACTICAL CONSEQUENCE IS UNCOMFORTABLE: ONCE A CONFIGURATION LANGUAGE OR TEMPLATE SYSTEM IS TURING COMPLETE, EVERY INTERESTING QUESTION ABOUT IT BECOMES UNDECIDABLE. You cannot in general determine whether a configuration will terminate, whether two configurations are equivalent, or whether a given rule can ever fire. This is why security-sensitive formats deliberately AVOID Turing completeness — and why some do not, to their cost.

The counting argument settles it without exhibiting a single example: there are countably many Turing machines and uncountably many languages, so almost every language is recognised by nothing at all. The computable is not merely a proper subset of the describable — it is a vanishingly small fragment of it.

🌍 Go further: Turing completeness is easy to achieve accidentally, and that is a security problem rather than a curiosity. A system needs only conditional branching and unbounded storage — and those turn up in C++ templates, recursive SQL, Conway's Game of Life, Minecraft redstone, and even the x86 MOV instruction on its own. The moment a configuration format or template system becomes Turing complete, every interesting question about it becomes undecidable: you cannot determine whether a config terminates, whether two are equivalent, or whether a rule can ever fire. This is why security-conscious formats deliberately restrict themselves below Turing completeness. Search "accidentally Turing complete configuration language security".

💡 Exam angle: be able to design a TM for aⁿbⁿcⁿ and explain why a PDA cannot do it — a stack is consumed as it is read, whereas a tape can be traversed repeatedly. Name the standard construction techniques, especially marking and shuttling. Know the LBA, that it recognises exactly the context-sensitive languages, and the configuration-counting argument |Q| × n × |Γ|ⁿ that makes context-sensitive membership decidable. Reproduce the full hierarchy with machines and separating languages, and be ready to give the countable-versus-uncountable argument for the existence of non-RE languages.

Syllabus points

Recursive & recursively enumerable languages
Designing a TM for a language

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.