TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
Open in the Padhaiko app4.3–4.5 TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions
4.3 Variants of Turing Machines
The standard deterministic single-tape Turing machine possesses substantial computational flexibility. Several variations exist in literature, all of which are computationally equivalent to the single-tape model: any language recognized or function computed by a variant can also be recognized or computed by a standard Turing machine.
Multi-Tape Turing Machine
A multi-tape Turing machine has a finite control connected to separate infinite tapes, each possessing its own independent read/write head.
Formally, a -tape Turing machine transition function is defined as:
In a single computational step, the machine:
- Reads the -tuple of symbols currently scanned by heads .
- Transitions from current state to next state .
- Overwrites each scanned cell with a corresponding symbol .
- Moves each head independently in its specified direction .
Initially, the input string is placed on the primary tape (Tape 1) with head 1 at the leftmost symbol, while tapes are completely blank.
Equivalence of Multi-Tape and Single-Tape Turing Machines
Every language acceptable by a -tape Turing machine in time is acceptable by a single-tape Turing machine in time .
Proof
The single-tape machine represents the tapes of using tracks on a single physical tape:
- For each tape , one track stores the actual tape symbols of Tape .
- A companion marker track contains a unique marker directly above the cell currently scanned by head .
To simulate one transition of :
- sweeps from the leftmost head marker to the rightmost head marker, collecting the -tuple of scanned symbols into its finite control state.
- Based on , makes a second sweep, updating each scanned symbol to and shifting the marker one position in direction .
- If any head marker moves into an unallocated blank cell, shifts all contents to the right by one cell to create space.
Because the distance between the leftmost and rightmost head markers in steps cannot exceed , each simulation step requires single-tape moves. Simulating steps takes at most total steps. Thus, multi-tape Turing machines recognize exactly the same class of languages as standard single-tape machines.
Other Prominent Turing Machine Variants
- Multi-Head Turing Machine: A single tape accessed by independent read/write heads. Simulated on a single-tape TM by storing head markers on distinct tracks.
- Off-Line Turing Machine: Features a dedicated read-only input tape (whose head cannot overwrite symbols) paired with one or more separate read/write work tapes.
- Multidimensional Turing Machine: The tape extends as an -dimensional grid (e.g. 2D grid with movements ). The cells are mapped to a 1D tape using coordinate tuples separated by delimiters.
- Nondeterministic Turing Machine (NDTM): The transition function maps to sets of alternatives:
An input is accepted if at least one computational path reaches an accept state. Every NDTM operating in time can be simulated by a deterministic 3-tape TM in time using breadth-first search across the computation tree.
- Storage in Finite Control: The state space is structured as Cartesian products , allowing the finite control to cache a fixed number of tape symbols internally without writing them to the tape.
- Turing Machine as Enumerator: An enumerator is a 2-tape TM with a write-only output tape. It starts on an empty tape and prints a sequence of words separated by delimiters. A language is recursively enumerable if and only if some enumerator enumerates it.
4.4 Unrestricted Grammar & The Chomsky Hierarchy
While automata serve as language recognizers/acceptors, formal grammars operate as language generators. In 1956, linguist Noam Chomsky categorized all generative grammars into a four-level hierarchy based on the structural constraints imposed upon their production rules.
+-------------------------------------------------------------+
| Type 0: Unrestricted Grammar |
| Language: Recursively Enumerable (RE) |
| Automaton: Turing Machine (TM) |
| +---------------------------------------------------------+ |
| | Type 1: Context-Sensitive Grammar (CSG) | |
| | Language: Context-Sensitive Language (CSL) | |
| | Automaton: Linear Bounded Automaton (LBA) | |
| | +-----------------------------------------------------+ | |
| | | Type 2: Context-Free Grammar (CFG) | | |
| | | Language: Context-Free Language (CFL) | | |
| | | Automaton: Pushdown Automaton (PDA) | | |
| | | +-------------------------------------------------+ | | |
| | | | Type 3: Regular Grammar | | | |
| | | | Language: Regular Language | | | |
| | | | Automaton: Deterministic Finite Automaton (DFA) | | | |
| | | +-------------------------------------------------+ | | |
| | +-----------------------------------------------------+ | |
| +---------------------------------------------------------+ |
+-------------------------------------------------------------+
The Four Chomsky Grammar Classes
A formal grammar is defined as where is the set of variables (non-terminals), is the set of terminals, is the production rules, and is the start symbol.
- Type 0: Unrestricted Grammar (Phase-Structure Grammar)
- Production format: where containing at least one non-terminal, and .
- Constraints: None. Arbitrary rewriting, replacement, and contraction are permitted.
- Generated Language: Recursively Enumerable (RE).
- Recognizing Automaton: Turing Machine.
- Type 1: Context-Sensitive Grammar (CSG)
- Production format: where (non-contracting property).
- Alternatively: with and (the replacement of variable depends on the surrounding context ).
- Exception: is permitted if does not appear on the right-hand side of any production.
- Generated Language: Context-Sensitive Language (CSL) (e.g. ).
- Recognizing Automaton: Linear Bounded Automaton (LBA) (a TM whose tape is bounded by a constant factor of the input length).
- Type 2: Context-Free Grammar (CFG)
- Production format: where (a single non-terminal) and .
- Generated Language: Context-Free Language (CFL) (e.g. ).
- Recognizing Automaton: Pushdown Automaton (PDA).
- Type 3: Regular Grammar (Right-Linear or Left-Linear)
- Right-linear format: or or , where and .
- Left-linear format: or or .
- Generated Language: Regular Language (e.g. ).
- Recognizing Automaton: Finite State Automaton (DFA / NFA).
4.5 Recursive Function Theory
While automata describe computation from an operational (mechanistic) viewpoint (specifying how states transition and heads shift), recursive function theory formulates computation axiomatic-declaratively (specifying what mathematical relation is defined).
Developed by Gödel, Kleene, and Church, recursive function theory proves that all effective algorithmic computations can be constructed from three primitive base functions using composition, primitive recursion, and unbounded search.
The Three Initial (Base) Functions
The initial functions operate over the natural numbers :
- Zero Function (): Maps any single natural argument to zero:
- Successor Function (): Returns the next natural integer:
- Projection Function (): Selects the -th coordinate from a -tuple ():
Examples: , , .
Fundamental Construction Operations
Composition and Primitive Recursion
New functions are formed from existing functions via two primary operations:
- Composition (Substitution): Given a function of arguments and functions each of arguments, the composite function is:
- Primitive Recursion: Given base function of arguments and inductive step function of arguments, function of arguments is defined by:
For single-variable functions, the base case is a constant :
Function Classifications
- Primitive Recursive Function: Any function obtained from the initial functions by a finite sequence of compositions and primitive recursions.
- All primitive recursive functions are total (defined for all input values) and strictly terminate.
- Standard arithmetic operations (addition, multiplication, exponentiation, factorial, predecessor, proper subtraction) are all primitive recursive.
- Ackermann's Function: A total computable function that grows faster than any primitive recursive function. It demonstrates that the class of primitive recursive functions is a strict subset of all computable functions:
- Partial Recursive Function (-Recursive Function): Obtained by augmenting composition and primitive recursion with the unbounded minimalization operator ():
which denotes the smallest such that . If no such exists, the search runs forever, making the function partial (undefined for that input).
- Total Recursive Function: A -recursive function that is defined on all inputs .
Turing–Kleene Equivalence Theorem
A mathematical function is partial recursive (-recursive) if and only if it is computable by a Turing machine.
Worked Out Examples
1
Design a 2-tape Turing machine that acts as a string copying transducer: given input on Tape 1, it outputs .
Using two tapes eliminates the head shuttling required by a single tape machine:
- Pass 1 (Read and Duplicate):
- The head on Tape 1 scans rightward across the input string .
- Simultaneously, head 2 writes each scanned character onto Tape 2 ().
- Both heads reach the trailing delimiter in steps. Tape 2 now holds an exact duplicate of .
- Pass 2 (Rewind Tape 2):
- Head 1 remains parked at the end of the original string on Tape 1.
- Head 2 rewinds leftward to the start of the copy on Tape 2.
- Pass 3 (Append Duplicate to Tape 1):
- Head 2 reads from Tape 2 moving right, while Head 1 writes those symbols sequentially onto Tape 1 directly following the delimiter.
- The entire duplication process completes in linear time , compared to on a single-tape TM.
The physical tape contents evolve through the following stages:
The 2-tape Turing machine duplicates the input string into in optimal linear time.
2
Construct an unrestricted grammar (Type 0) to generate the language:
Show the derivations for the strings and .
Let where , , and the productions are:
- Rules 1 and 2 generate equal numbers of 's, 's, and 's, placing in position while leaving 's and 's interleaved.
- Rule 3 () is an unrestricted / context-sensitive permutation rule that shifts all 's to the left of all 's.
- Rules 4–7 convert uppercase non-terminals and into lowercase terminals and in left-to-right order.
The unrestricted grammar generates exactly through non-terminal generation, sorting by , and terminal conversion.
3
Design Turing machines to implement the two initial functions of recursive function theory:
- The Zero function for in unary.
- The Successor function for in unary.
In unary, integer is represented as ones (). The zero function must erase the entire input block, replacing all 's with blank :
- State scans rightward, rewriting each with ().
- When blank is reached, the head stops and enters accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | B | R |
| →q0 | B | q2 | B | S |
- Machine-checked
- ✓ 1111 → ε
- ✓ 11 → ε
- ✓ 1 → ε
The successor function maps by appending one additional at the end of the input string:
- State traverses rightward across all existing 's ().
- At the trailing blank , it writes and enters accept state without moving further ().
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | h | 1 | S |
- Machine-checked
- ✓ 111 → 1111
- ✓ 1 → 11
- ✓ 11 → 111
The zero function is implemented by an eraser Turing machine that converts , and the successor function is implemented by an incrementing Turing machine that appends a tally mark.
4
Prove that standard integer addition , multiplication , predecessor , and proper subtraction are all primitive recursive functions.
Addition is defined by primitive recursion on the second argument :
where . Since base function , projection , and successor are initial functions, is primitive recursive.
Multiplication is defined by primitive recursion using the previously established function:
where . Since is an initial function and is primitive recursive, is primitive recursive.
The predecessor function (where ):
Proper subtraction :
where . Both functions are formed solely by composition and primitive recursion from initial functions, proving they are primitive recursive.
Addition, multiplication, predecessor, and proper subtraction are rigorously proven to be primitive recursive functions via formal induction equations.
Exercises
Exercises
Explain the configuration and working of a multi-tape Turing machine.
Multi-Tape Architecture and Components: A -tape Turing machine () consists of:
- A single finite-state control storing the active state .
- Exactly independent, linear memory tapes, unbounded in extent, each divided into cells holding symbols from alphabet .
- Exactly independent read/write heads (), where head scans and writes exclusively on Tape .
+-------------------------------+
| Finite Control (Q, δ) |
| Current State: q |
+-------------------------------+
| | |
(Head 1) (Head 2) (Head k)
v v v
Tape 1: [ a ][ b ][ a ][ B ] ... (Input Tape)
Tape 2: [ B ][ B ][ B ][ B ] ... (Work Tape 1)
Tape k: [ B ][ B ][ B ][ B ] ... (Work Tape k-1)
Initially, Tape 1 holds the input string with Head 1 on the first symbol; all other tapes are completely filled with blanks , and their heads point to cell 0.
Transition Mechanics and Working Step: The transition function for a -tape TM is defined as:
At each discrete clock step:
- The finite control reads the -tuple of symbols currently scanned by Heads .
- Consulting , the machine:
- Changes internal control state from to .
- Simultaneously writes symbol onto Tape under Head for each .
- Independently shifts each Head in direction .
Computational Equivalence and Algorithmic Efficiency: A multi-tape Turing machine is computationally equivalent to a standard single-tape Turing machine:
Every language recognized by a -tape TM can be recognized by a single-tape TM. However, multiple tapes drastically improve time efficiency: operations such as copying a string of length or recognizing palindromes take time on a single tape due to head shuttling, but take only linear time on a multi-tape TM.
A multi-tape Turing machine consists of a single finite-state control linked to independent linear tapes. Each tape possesses its own bidirectional read/write head. In each computational step, the machine reads the -tuple of symbols under all heads, transitions to a new internal state, writes a -tuple of replacement symbols across all tapes, and independently shifts each head left (), right (), or stationary (). Tape 1 initially holds the input, while remaining tapes are blank work tapes.
How is a Turing machine helpful with storage in states?
Concept of State-Based Storage: In a standard Turing machine, internal states merely record the control flow phase of an algorithm. However, because the state set can be any finite set, the finite control can be structured to buffer a finite amount of auxiliary information directly inside the active state without writing it to the tape.
Mathematical Formulation (Cartesian Product of States): To store symbols in memory, the state set is structured as a Cartesian product:
where represents the primary control states (phases) and each is a finite data alphabet. A composite state is denoted:
where indicates the current execution stage, and each holds a buffered symbol or flag. Because and all are finite sets, the product set remains strictly finite, complying with the standard formal definition of a Turing machine.
Practical Applications:
- Comparing Boundary Symbols (Palindromes): When reading the leftmost symbol of a string, transitioning to state or buffers the symbol in the state. Upon moving to the right end, the machine compares the scanned symbol directly against the symbol stored in the state.
- Arithmetic Carry Buffering: In multi-digit binary addition, state denotes the addition step with carry , while denotes addition with carry .
- Lookahead Buffering: Holding the previously read symbol in the state allows a 1-character lookahead without extra tape movements.
Storage in states allows the finite control of a Turing machine to remember a finite amount of auxiliary data without writing it to the tape. The state set is structured as a Cartesian product , where an element represents the current control state alongside buffered symbols . This technique allows a TM to perform comparisons, carry arithmetic flags, and buffer lookahead symbols directly in its internal state.
Explain how a multi-tape Turing machine can be simulated using a single-tape Turing machine.
Multi-Track Representation with Head Markers: To simulate a -tape TM with heads on a single-tape TM , the tape of is divided into virtual tracks:
- Tracks store the contents of Tapes of .
- Tracks store head marker flags: a marked symbol (e.g. ) marks the position of Head on Tape .
Track 1: [ a ][ b ][ a ][ b ] (Contents of Tape 1)
Track 2: [ ][ ^ ][ ][ ] (Head 1 marker: cell 1)
Track 3: [ 0 ][ 1 ][ 1 ][ ] (Contents of Tape 2)
Track 4: [ ^ ][ ][ ][ ] (Head 2 marker: cell 0)
The tape alphabet of is . Since and are finite, is finite.
Simulating One Step of the Multi-Tape Machine: Machine simulates a single transition of in two sweeps:
- Gathering Sweep (Left to Right): Starting from the leftmost head marker, 's single head sweeps rightward until it visits all head markers. As it encounters each marker , it buffers symbol in its control state using storage in states: .
- Transition Lookup: Once all symbols are buffered, consults 's transition rule:
- Execution Sweep (Right to Left): sweeps back across the tape:
- Overwrites symbol with replacement on Track .
- Shifts the head marker on Track one cell in direction .
- If a head marker moves into an unallocated blank cell, shifts all symbols rightward by one cell to create space.
- updates its internal control state to , completing the simulation of one step.
Time Complexity Bound ():
To simulate one transition of , machine makes sweeps over at most tape cells, taking steps. The total time to simulate an entire -step computation is:
Thus, any multi-tape computation running in polynomial time is simulated in polynomial time on a single tape.
A -tape TM is simulated by a single-tape TM with tracks. Tracks hold the contents of the tapes, while tracks contain head markers () denoting the current head position on each tape. To simulate one move, the single-tape head sweeps across the active region to identify all scanned symbols, updates its control state, and makes a return sweep to overwrite symbols and shift head markers. A -time multi-tape computation is simulated in time on a single tape.
Explain how a Turing machine works as an enumerator.
Architecture of an Enumerator: An enumerator is a Turing machine variant configured to systematically list (enumerate) strings of a language:
- It possesses a finite state control.
- It has an internal bidirectional read/write work tape (initially empty).
- It has a write-only, one-directional output tape (or print stream).
+-------------------------------+
| Finite Control |
+-------------------------------+
| (Read/Write) | (Write-Only Print)
v v
Work Tape: [ B ][ a ][ 1 ] ...
Output Tape: # w1 # w2 # w3 # ... (Strings printed sequentially)
The enumerator begins execution with an empty work tape and without any initial input string.
Working Mechanism:
- The machine begins computing autonomously according to its transition rules.
- At various points in its computation, whenever it generates a string belonging to the language, it prints the string onto the output tape separated by boundary markers (e.g. ).
- Strings may be printed in any order, repetitions are permitted, and for infinite languages, the enumeration process runs indefinitely.
The language enumerated by , denoted , is the set of all strings that eventually appear on its output tape:
Equivalence with Recursively Enumerable Languages: Theorem: A language is recursively enumerable (Turing-recognizable) if and only if some enumerator enumerates .
Conversely, if an enumerator exists for , a recognizer for input simply runs and monitors the output stream: if appears, halts and accepts.
An enumerator is a Turing machine equipped with a work tape and a separate write-only output tape. It begins execution with an empty tape. During its computation, it writes strings over its alphabet onto the output tape separated by boundary markers (e.g. ). The strings may be enumerated in any order and with repetitions. The set of all strings printed on the output tape constitutes the language enumerated by the machine; a language is recursively enumerable if and only if it can be enumerated by some enumerator.
How can a Turing machine be used to describe the zero function and successor function as defined in initial functions?
Unary Representation of Natural Numbers: In computability theory, non-negative integers are represented on a Turing machine tape using unary notation as contiguous blocks of tally marks ():
- corresponds to tallies (empty string / all blanks ).
- corresponds to .
- corresponds to , and in general .
A Turing machine computes an arithmetic function by transforming initial configuration into halting configuration .
Turing Machine for the Zero Function : The Zero function maps any input to zero: . In unary, the machine must erase all 's on the tape, replacing each with blank :
- State reads rightward, overwriting each with blank ().
- When the first trailing blank is reached, the tape is completely cleared, and the machine halts in accept state ().
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | B | R |
| →q0 | B | q2 | B | S |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 1
- ✓ accepts 11
- ✓ accepts 111
- ✓ rejects 0
- ✓ rejects 01
- ✓ rejects a
- ✓ 1111 → ε
- ✓ 11 → ε
- ✓ 1 → ε
Trace on input ():
The tape is left completely blank, correctly representing .
Turing Machine for the Successor Function : The Successor function increments input by 1: . In unary, this corresponds to mapping by appending one additional at the end of the input block:
- State scans rightward across all existing 's without modification ().
- At the trailing blank , it writes and halts in state ().
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | h | 1 | S |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 1
- ✓ accepts 11
- ✓ accepts 111
- ✓ rejects 0
- ✓ rejects 01
- ✓ rejects a
- ✓ 111 → 1111
- ✓ 1 → 11
- ✓ 11 → 111
Trace on input ():
The resulting tape holds (), correctly computing .
In unary arithmetic, natural number is represented by tally marks (). The zero function is implemented by an eraser Turing machine that scans the input block , overwrites every with blank , and halts in an empty configuration. The successor function is implemented by an incrementing Turing machine that scans past the tallies to the trailing blank , writes an additional , and halts, leaving on the tape.
Describe the working mechanism of a multi-tape Turing machine. How does it differ from a multiple-head Turing machine?
Working Mechanism of Multi-Tape Turing Machine: A -tape TM possesses completely separate physical tapes, each accessed by exactly one dedicated read/write head. In each computational step, the finite control reads the -tuple of symbols scanned under all heads, changes state, writes replacement symbols simultaneously across the tapes, and moves each head independently (). Each tape provides an independent linear address space: operations on Tape 1 have no direct physical connection to the cells or contents of Tape 2.
Working Mechanism of Multiple-Head Turing Machine: A -head TM has only one single physical tape, but that single tape is accessed simultaneously by independent read/write heads (). All heads scan, write, and shift on the exact same linear medium. This introduces the phenomenon of head collision: multiple heads may simultaneously scan the same tape square. A deterministic multiple-head TM must resolve write-conflicts (for instance, by prioritizing the head with the lowest index).
Comparison Summary:
| Feature | Multi-Tape Turing Machine | Multiple-Head Turing Machine |
|---|---|---|
| Number of Tapes | distinct, independent tapes | Exactly 1 physical tape |
| Number of Heads | heads (exactly 1 head per tape) | heads (all on the same tape) |
| Head Collisions | Impossible (each tape has only 1 head) | Possible (heads can scan the same cell) |
| Memory Isolation | Completely separate memory channels | Shared memory on a common tape |
| Simulated on 1-Tape TM | Simulated via tracks in time | Simulated via head markers on tracks |
| Computational Power | Equivalent to standard single-tape TM | Equivalent to standard single-tape TM |
Both models accept exactly the class of recursively enumerable languages.
A multi-tape Turing machine has distinct tapes, each accessed by exactly one read/write head. A multiple-head Turing machine has only one single physical tape, but that single tape is simultaneously scanned and manipulated by independent read/write heads. While multiple heads on a single tape can collide or read the same cell, multiple tapes allow completely independent spatial workspaces. Both architectures are computationally equivalent to the standard single-tape TM.
What is a primitive recursive function?
Formal Definition and Base Initial Functions: A function is a primitive recursive function if it can be constructed from a basic set of initial functions through a finite number of applications of composition and primitive recursion.
The three families of Initial (Base) Functions are:
- Zero Function :
- Successor Function :
- Projection Functions (for ):
Construction Operations:
- Function Composition: Given and , their composition is:
- Primitive Recursion: Given and , function is defined recursively on its last argument :
(For , the base case is a constant .)
Properties and Computability Boundary:
- Totality: Every primitive recursive function is total (defined for all arguments in ) and guaranteed to terminate in finite steps.
- Turing Computability: Every primitive recursive function is computable by a deterministic Turing machine.
A primitive recursive function is a function that can be built from the initial base functions (Zero function , Successor function , and Projection functions ) by a finite number of applications of function composition and primitive recursion. All primitive recursive functions are total, strictly terminating, and Turing-computable.