Turing Machines: Representation, Moves & Computing
Open in the Padhaiko app4.1–4.2 Turing Machines: Representation, Moves & Computing
4.1 Introduction to Turing Machine
Finite automata model devices with finite internal memory. Pushdown automata model devices equipped with an unbounded stack accessed strictly in Last-In First-Out (LIFO) order. Neither model qualifies as a universal model for computation, as neither can recognize context-sensitive languages such as .
The Turing machine (TM), introduced by Alan Turing in 1936, is an accurate and robust mathematical model of a general-purpose digital computer. A Turing machine possesses an infinite storage tape and a two-way read/write head, giving it unrestricted random-access read and write capabilities. Any algorithmic computation executable on modern electronic hardware can be performed by a Turing machine.
Turing Machine (Formal 7-Tuple Definition)
A deterministic Turing machine is formally defined as a 7-tuple:
where:
- is a finite, non-empty set of internal states.
- is a finite set of input symbols (the input alphabet), such that .
- is a finite set of tape symbols (the tape alphabet), where .
- is the transition function mapping:
(or where stationary move is modeled as a two-step transition).
- is the initial (start) state.
- is the designated blank symbol.
- is the set of final (accepting) states.
Physical Components of a Turing Machine
A Turing machine consists of three structural elements:
- Infinite Tape: Divided into discrete cells, extending infinitely in both directions (or semi-infinitely to the right). Each cell stores exactly one tape symbol from . Initially, the input string is placed in consecutive cells, and all remaining cells hold the blank symbol .
- Read/Write Head: Scans one cell of the tape at any given moment. It can read the symbol in the scanned cell, overwrite it with a symbol from , and translate one cell to the left (), one cell to the right (), or remain stationary ().
- Finite Control Unit: Operates in discrete clock steps. In state scanning symbol , the control consults to transition to state , write , and shift direction .
4.2 Instantaneous Description & Machine Moves
Instantaneous Description (ID) of a Turing Machine
The complete computational state or configuration of a Turing machine at any discrete step is captured by an Instantaneous Description (ID).
An ID is written as (or ), where:
- is the current state of the machine.
- represents the contents of the tape from the leftmost non-blank symbol up to (but not including) the scanned cell.
- represents the contents of the tape from the scanned cell through the rightmost non-blank symbol. The head is actively scanning the first symbol of .
The step relation denotes a single machine transition:
- Right Move: If , then:
- Left Move: If and with , then:
- Stationary Move: If , then:
The reflexive-transitive closure denotes a finite sequence of zero or more consecutive moves.
4.3 Representation of a Turing Machine
A Turing machine is represented either by a transition diagram (state diagram) or by a transition table (state table).
In a transition diagram:
- Nodes represent the states .
- A directed edge from state to state labeled indicates that if is in state and reads symbol , it writes , moves the head in direction , and enters state .
- An arrow with no source designates the start state .
- Double concentric circles denote accepting states in .
4.4 Computing with a Turing Machine
A Turing machine operates in two principal modes:
- Language Acceptor (Decider/Recognizer): Given an input string , the machine starts in initial configuration . If halts in an accept state , is accepted (). If halts in a non-accepting state or loops infinitely, is rejected. If halts on all inputs, it is a decider, and is a recursive (Turing-decidable) language.
- Transducer (Function Computer): Given arguments encoded on the tape (typically in unary notation where integer is represented by or tallies, or in binary), the machine halts with the output string left on the tape:
Functions computable by such Turing machines are called Turing-computable or partial recursive functions.
Worked Out Examples
1
Design a Turing machine to accept the language of equal 's followed by equal 's:
Trace its execution on the input string .
The strategy matches the leftmost unmarked with the leftmost unmarked :
- In state , scan the tape. Replace the first with , transition to , and move right across remaining 's and already marked 's until finding the first unmarked .
- Replace that with , transition to , and move left across 's and 's until encountering the marker .
- Move one cell right of back into state , and repeat the cycle for the next .
- When reads instead of , all 's have been paired. Transition to and scan right over all 's to verify no stray symbols remain before the blank . Reaching blank in transitions to accept state .
Let .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | Y | q3 | Y | R |
| q1 | Y | q1 | Y | R |
| q1 | a | q1 | a | R |
| q1 | b | q2 | Y | L |
| q2 | Y | q2 | Y | L |
| q2 | a | q2 | a | L |
| q2 | X | q0 | X | R |
| q3 | Y | q3 | Y | R |
| q3 | B | q4 | B | S |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aabb
- ✓ accepts aaabbb
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects aab
- ✓ rejects abb
The sequence of instantaneous descriptions is:
The Turing machine correctly accepts . The configuration halts in accept state on valid strings and fails or hangs on strings not in .
2
Design a Turing machine to recognize the non-context-free language:
- In state , replace the leftmost with and shift right in state .
- In state , scan past remaining 's and marked 's to find the leftmost . Replace it with and move right in state .
- In state , scan past remaining 's and marked 's to find the leftmost . Replace it with and move left in state .
- In state , traverse leftward past all 's, 's, 's, 's, and 's until reaching . Move one cell right back into state .
- When encounters , all 's are exhausted. State verifies all 's are marked , state verifies all 's are marked , and seeing blank confirms the string is accepted in .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | Y | q4 | Y | R |
| q1 | Y | q1 | Y | R |
| q1 | a | q1 | a | R |
| q1 | b | q2 | Y | R |
| q2 | Z | q2 | Z | R |
| q2 | b | q2 | b | R |
| q2 | c | q3 | Z | L |
| q3 | Z | q3 | Z | L |
| q3 | a | q3 | a | L |
| q3 | Y | q3 | Y | L |
| q3 | b | q3 | b | L |
| q3 | X | q0 | X | R |
| q4 | Y | q4 | Y | R |
| q4 | Z | q5 | Z | R |
| q5 | Z | q5 | Z | R |
| q5 | B | q6 | B | S |
- Machine-checked
- ✓ accepts abc
- ✓ accepts aabbcc
- ✓ accepts aaabbbccc
- ✓ rejects ab
- ✓ rejects abcde
- ✓ rejects aabbc
- ✓ rejects aabcc
- ✓ rejects cba
The 7-state Turing machine accepts by sequentially marking corresponding triples and halting in state .
3
Design a Turing machine as a transducer to compute the 1's complement of an arbitrary binary string (e.g. ).
- In state , read each bit from left to right: replace with , and replace with .
- Upon reaching the right-hand blank , transition to state and scan leftwards across the inverted bits.
- Upon reaching the left-hand blank , move right one position into accept state , leaving the head poised at the most significant bit of the complemented result.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 1 | R |
| →q0 | 1 | q0 | 0 | R |
| →q0 | B | q1 | B | L |
| q1 | 0 | q1 | 0 | L |
| q1 | 1 | q1 | 1 | L |
| q1 | B | q2 | B | R |
- Machine-checked
- ✓ 1011 → 0100
- ✓ 1100 → 0011
- ✓ 0 → 1
- ✓ 1 → 0
The machine inverts every binary bit and restores the head to the starting position in state , correctly outputting the 1's complement.
4
Design a Turing machine to compute the 2's complement of any binary string (e.g. , ).
By binary arithmetic, the 2's complement of a binary number is obtained by scanning from right to left:
- Leave all trailing 's unchanged.
- Leave the least significant unchanged.
- Invert all remaining bits to the left of that first ( and ).
Implementation steps:
- : Move right to the end of the input string until encountering blank . Step left into .
- : Move left over trailing zeros (). When the first is encountered, keep it () and transition to .
- : Invert all subsequent bits to the left ( and ) until reaching the blank . Step right into accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | 0 | q0 | 0 | R |
| →q0 | B | q1 | B | L |
| q1 | 0 | q1 | 0 | L |
| q1 | 1 | q2 | 1 | L |
| q2 | 1 | q2 | 0 | L |
| q2 | 0 | q2 | 1 | L |
| q2 | B | q3 | B | R |
- Machine-checked
- ✓ 1011 → 0101
- ✓ 1100 → 0100
- ✓ 10 → 10
- ✓ 1 → 1
The Turing machine computes the exact 2's complement representation in state .
5
Design a Turing machine to accept the language of even-length palindromes:
- In state , read the leftmost symbol:
- If , mark with and transition to .
- If , mark with and transition to .
- If or , all symbols have matched; transition to accept state .
- State moves right to the end of the string (blank or marker ), shifts left into , and checks that the matching symbol is . It replaces it with and transitions to .
- State moves right to the end of the string, shifts left into , and checks that the matching symbol is . It replaces it with and transitions to .
- State travels all the way left until hitting marker , steps right, and returns to .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | b | q4 | X | R |
| →q0 | X | q6 | X | R |
| q1 | a | q1 | a | R |
| q1 | b | q1 | b | R |
| q1 | B | q2 | B | L |
| q1 | X | q2 | X | L |
| q2 | a | q3 | X | L |
| q3 | a | q3 | a | L |
| q3 | b | q3 | b | L |
| q3 | X | q0 | X | R |
| q4 | a | q4 | a | R |
| q4 | b | q4 | b | R |
| q4 | X | q5 | X | L |
| q4 | B | q5 | B | L |
| q5 | b | q3 | X | L |
- Machine-checked
- ✓ accepts aa
- ✓ accepts bb
- ✓ accepts abba
- ✓ accepts baab
- ✓ accepts aabbaa
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aba
- ✓ rejects aab
- ✓ rejects bab
The machine matches outer pairs inward and halts in accepting state if and only if the input is an even-length palindrome.
6
Design a Turing machine to accept the language of odd-length palindromes over :
The machine pairs outer symbols inward:
- In state , read the leftmost symbol:
- If , mark with and move right into .
- If , mark with and move right into .
- In (or ), scan rightward to the right end of the unexamined string (marked by blank or previous marker ), shift left into (or ).
- In (expecting ), if it reads , mark with and return leftward in to the start marker. If it reads immediately upon shifting left, only the single center character was present; transition directly to accept state .
- Similarly in (expecting ), if it reads , mark with and return leftward in ; if it reads , accept directly in .
- In state , scan left to the leftmost marker , step right, and repeat from .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | b | q4 | X | R |
| q1 | a | q1 | a | R |
| q1 | b | q1 | b | R |
| q1 | B | q2 | B | L |
| q1 | X | q2 | X | L |
| q2 | a | q3 | X | L |
| q2 | X | q6 | X | R |
| q3 | a | q3 | a | L |
| q3 | b | q3 | b | L |
| q3 | X | q0 | X | R |
| q4 | a | q4 | a | R |
| q4 | b | q4 | b | R |
| q4 | X | q5 | X | L |
| q4 | B | q5 | B | L |
| q5 | b | q3 | X | L |
| q5 | X | q6 | X | R |
- Machine-checked
- ✓ accepts a
- ✓ accepts b
- ✓ accepts aaa
- ✓ accepts aba
- ✓ accepts bab
- ✓ accepts bbb
- ✓ accepts ababa
- ✓ rejects aa
- ✓ rejects bb
- ✓ rejects ab
- ✓ rejects ba
- ✓ rejects abba
- ✓ rejects aab
The machine verifies symmetrical outer characters surrounding the isolated middle symbol and halts in state .
7
Design a Turing machine that increments an arbitrary binary string by 1 (i.e. computes ).
Adding 1 to a binary integer:
- : Move right across all digits to locate the least significant bit adjacent to blank .
- : Step left. If the bit is , turn it to and carry leftward (). If the bit is or blank , change it to and terminate the carry ( or ), entering .
- : Move right to the trailing blank and step left into accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | 0 | q0 | 0 | R |
| →q0 | B | q1 | B | L |
| q1 | 1 | q1 | 0 | L |
| q1 | 0 | q2 | 1 | R |
| q1 | B | q2 | 1 | R |
| q2 | 1 | q2 | 1 | R |
| q2 | 0 | q2 | 0 | R |
| q2 | B | q3 | B | L |
- Machine-checked
- ✓ 0 → 1
- ✓ 101 → 110
- ✓ 111 → 1000
- ✓ 1011 → 1100
The machine handles all carry propagation (including length expansion such as ) and halts in state .
8
Design a Turing machine to accept the language of arbitrary palindromes (even or odd length):
The machine generalizes palindrome matching by allowing both an even fold (where the central character is ) and an odd fold (where the central character is or ):
- accepts the empty string or fully matched even palindromes.
- and accept when the final unmatched middle character is isolated.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | b | q4 | X | R |
| →q0 | X | q6 | X | R |
| q1 | a | q1 | a | R |
| q1 | b | q1 | b | R |
| q1 | B | q2 | B | L |
| q1 | X | q2 | X | L |
| q2 | a | q3 | X | L |
| q2 | X | q7 | X | R |
| q3 | a | q3 | a | L |
| q3 | b | q3 | b | L |
| q3 | X | q0 | X | R |
| q4 | a | q4 | a | R |
| q4 | b | q4 | b | R |
| q4 | X | q5 | X | L |
| q4 | B | q5 | B | L |
| q5 | b | q3 | X | L |
| q5 | X | q7 | X | R |
- Machine-checked
- ✓ accepts aa
- ✓ accepts bb
- ✓ accepts aba
- ✓ accepts bab
- ✓ accepts abba
- ✓ accepts baab
- ✓ accepts ababa
- ✓ rejects ab
- ✓ rejects ba
- ✓ rejects aab
- ✓ rejects abb
The machine accepts both even- and odd-length palindromic strings over .
9
Design a Turing machine that reads a binary string: if the string represents an odd number, it subtracts 1; if it represents an even number, it adds 1.
The parity of a binary number depends entirely on its least significant bit (LSB):
- If the LSB is (odd), subtracting 1 toggles the LSB from to . All higher bits remain unchanged.
- If the LSB is (even), adding 1 toggles the LSB from to . All higher bits remain unchanged.
Thus, the machine only needs to locate the LSB and invert it.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 0 | R |
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | q1 | B | L |
| q1 | 1 | h | 0 | S |
| q1 | 0 | h | 1 | S |
- Machine-checked
- ✓ 101 → 100
- ✓ 100 → 101
- ✓ 1110 → 1111
- ✓ 1111 → 1110
The machine scans to the end of the binary string, inverts the least significant bit in state , and halts immediately in state .
10
Design a single-tape deterministic Turing machine that counts the number of 's in a binary tape. If the count is even, it replaces every with ; if odd, it replaces every with .
- State represents an even parity of 's seen so far; represents odd parity.
- The machine scans rightward:
- In : reading stays in ; reading flips to .
- In : reading stays in ; reading flips to .
- When blank is reached:
- From (even count of 1's): move left into . In , scan leftward replacing every with .
- From (odd count of 1's): move left into . In , scan leftward replacing every with .
- Reaching the leading blank transitions into halt state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 0 | R |
| →q0 | 1 | q1 | 1 | R |
| q1 | 0 | q1 | 0 | R |
| q1 | 1 | q0 | 1 | R |
| →q0 | B | q2 | B | L |
| q1 | B | q3 | B | L |
| q2 | 1 | q2 | 0 | L |
| q2 | 0 | q2 | 0 | L |
| q3 | 0 | q3 | 1 | L |
| q3 | 1 | q3 | 1 | L |
| q2 | B | h | B | R |
| q3 | B | h | B | R |
- Machine-checked
- ✓ 10111 → 00000
- ✓ 11001 → 11111
- ✓ 000 → 000
- ✓ 11 → 00
The machine correctly tests the parity of 1-bits and transforms the entire tape according to the problem specification.
11
Design a Turing machine to recognize all strings of even length over the alphabet .
A 2-state modulo-2 counter tracks string length:
- State corresponds to an even number of characters read (including length 0).
- State corresponds to an odd number of characters read.
- When blank is encountered in state , the input has even length and the machine halts in accept state . If blank is seen in , no transition is defined and the string is rejected.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | a | R |
| →q0 | b | q1 | b | R |
| q1 | a | q0 | a | R |
| q1 | b | q0 | b | R |
| →q0 | B | h | B | S |
- Machine-checked
- ✓ accepts ε
- ✓ accepts aa
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts bb
- ✓ accepts abab
- ✓ accepts baba
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aba
- ✓ rejects bab
- ✓ rejects aaa
The machine accepts all strings with and rejects all odd-length strings.
12
Design a Turing machine to copy an arbitrary string over , transforming .
To duplicate string :
- In state , read the next character of :
- If , mark with and shift right into .
- If , mark with and shift right into .
- If blank , all original characters have been copied; step left into to restore markers and .
- State moves past the original string and the separating blank to deposit an at the end of the duplicate.
- State moves past the original string and the separating blank to deposit a at the end of the duplicate.
- States scan leftward across both copies to return to the marker in , step right, and repeat.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | b | q2 | Y | R |
| →q0 | B | q7 | B | L |
| q1 | a | q1 | a | R |
| q1 | b | q1 | b | R |
| q1 | B | q3 | B | R |
| q2 | a | q2 | a | R |
| q2 | b | q2 | b | R |
| q2 | B | q4 | B | R |
| q3 | a | q3 | a | R |
| q3 | b | q3 | b | R |
| q3 | B | q5 | a | L |
| q4 | a | q4 | a | R |
| q4 | b | q4 | b | R |
| q4 | B | q5 | b | L |
| q5 | a | q5 | a | L |
| q5 | b | q5 | b | L |
| q5 | B | q6 | B | L |
| q6 | a | q6 | a | L |
| q6 | b | q6 | b | L |
| q6 | X | q0 | X | R |
| q6 | Y | q0 | Y | R |
| q7 | Y | q7 | b | L |
| q7 | X | q7 | a | L |
| q7 | B | h | B | R |
- Machine-checked
- ✓ a → aBa
- ✓ b → bBb
- ✓ ab → abBab
The machine duplicates string separated by blank , leaving the tape in configuration and halting in state .
13
Design a Turing machine to compute the arithmetic doubling function using unary representation ( represented by ones).
For each in the input, the machine appends two 's at the end of the output area:
- State replaces the leftmost of with and enters . If it reads blank , all inputs are processed, entering .
- In , the head moves past the separating blank to the end of the copied block, appends a in and another in .
- States return the head leftward to the marker , move right, and repeat from .
- In state , the machine clears all temporary markers, converting them to blanks so that only the doubled ones remain on the tape.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q1 | X | R |
| →q0 | B | q6 | B | L |
| q1 | 1 | q1 | 1 | R |
| q1 | B | q2 | B | R |
| q2 | 1 | q2 | 1 | R |
| q2 | B | q3 | 1 | R |
| q3 | B | q4 | 1 | L |
| q4 | 1 | q4 | 1 | L |
| q4 | B | q5 | B | L |
| q5 | 1 | q5 | 1 | L |
| q5 | X | q0 | X | R |
| q6 | X | q6 | B | L |
| q6 | B | qh | B | L |
- Machine-checked
- ✓ 1 → 11
- ✓ 11 → 1111
- ✓ 111 → 111111
The Turing machine computes , producing tally marks for any input of tally marks.
14
Design a Turing machine to compute the successor-by-two function for in unary representation ( represented by ).
To compute :
- In state , scan rightward across the tally marks ().
- Upon reaching the terminating blank , write , step right, and enter .
- In state , write another , step stationary (), and enter accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | q1 | 1 | R |
| q1 | B | q2 | 1 | S |
- Machine-checked
- ✓ 1 → 111
- ✓ 11 → 1111
- ✓ 111 → 11111
The machine appends two 's to the right of the input block, correctly computing .
15
Design a Turing machine to compute unary addition:
where the inputs and are presented as .
Two unary numbers separated by a single blank can be added in steps:
- In state , scan rightward across the first block of ones ().
- When the separator blank is reached, replace it with and enter . The tape now contains ones.
- In , move right to the end of the second block until encountering blank . Step left into .
- In , erase the surplus by replacing it with blank , and halt in state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | q1 | 1 | R |
| q1 | 1 | q1 | 1 | R |
| q1 | B | q2 | B | L |
| q2 | 1 | h | B | S |
- Machine-checked
- ✓ 1B1 → 11
- ✓ 11B111 → 11111
- ✓ 111B11 → 11111
The machine fills the internal blank and removes one boundary tally, leaving exactly consecutive ones on the tape.
16
Design a Turing machine to compute the projection function in unary notation ().
- In state , erase the first argument by replacing each with blank ().
- When the separating blank is reached, step right into .
- In state , scan rightward across the remaining tallies ().
- Reaching the trailing blank halts in state , leaving only the tallies on the tape.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q0 | B | R |
| →q0 | B | q1 | B | R |
| q1 | 1 | q1 | 1 | R |
| q1 | B | h | B | S |
- Machine-checked
- ✓ 1B1 → 1
- ✓ 111B11 → 11
- ✓ 11B1111 → 1111
The machine erases the initial block of ones, leaving the second argument intact on the tape.
17
Design a Turing machine to compute the multiplication function in unary representation.
Given input :
- For each of the tallies in the first argument, make a complete copy of the tallies at the end of the tape.
- Maintain loop counters using tape markers: overwrite one of with , then iterate over each of , marking it and writing a into the product zone.
- Once all are copied, restore and repeat for the next of .
- When is exhausted, clean up markers and halt.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 1 | q1 | B | R |
| →q0 | B | q9 | B | R |
| q1 | 1 | q1 | 1 | R |
| q1 | B | q2 | B | R |
| q2 | 1 | q3 | X | R |
| q2 | B | q7 | B | L |
| q3 | 1 | q3 | 1 | R |
| q3 | B | q4 | B | R |
| q4 | 1 | q4 | 1 | R |
| q4 | B | q5 | 1 | L |
| q5 | 1 | q5 | 1 | L |
| q5 | B | q6 | B | L |
| q6 | 1 | q6 | 1 | L |
| q6 | X | q2 | X | R |
| q7 | X | q7 | 1 | L |
| q7 | B | q8 | B | L |
| q8 | 1 | q8 | 1 | L |
| q8 | B | q0 | B | R |
| q9 | 1 | q9 | B | R |
| q9 | B | h | B | R |
- Machine-checked
- ✓ 1B1 → 1
- ✓ 11B11 → 1111
- ✓ 11B111 → 111111
The Turing machine computes , producing tallies for inputs and .
18
Design a Turing machine to accept the language:
- In state , replace the leftmost with and move right into .
- In , skip 's and marked 's to find the leftmost ; mark it and enter .
- In , skip 's and marked 's to find the leftmost ; mark it and enter .
- In , skip 's and marked 's to find the leftmost ; mark it and enter .
- In , move all the way left past until reaching marker . Step right into to begin the next pass.
- When sees marker (no more 's), states verify that all 's, 's, and 's have been consumed, halting in accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | W | R |
| →q0 | X | q5 | X | R |
| q1 | X | q1 | X | R |
| q1 | a | q1 | a | R |
| q1 | b | q2 | X | R |
| q2 | b | q2 | b | R |
| q2 | Y | q2 | Y | R |
| q2 | c | q3 | Y | R |
| q3 | Z | q3 | Z | R |
| q3 | c | q3 | c | R |
| q3 | d | q4 | Z | L |
| q4 | Z | q4 | Z | L |
| q4 | a | q4 | a | L |
| q4 | X | q4 | X | L |
| q4 | b | q4 | b | L |
| q4 | Y | q4 | Y | L |
| q4 | c | q4 | c | L |
| q4 | W | q0 | W | R |
| q5 | X | q5 | X | R |
| q5 | Y | q6 | Y | R |
| q6 | Y | q6 | Y | R |
| q6 | Z | q7 | Z | R |
| q7 | Z | q7 | Z | R |
| q7 | B | q8 | B | S |
- Machine-checked
- ✓ accepts abcd
- ✓ accepts aabbccdd
- ✓ accepts aaabbbcccddd
- ✓ rejects abc
- ✓ rejects aabcdd
- ✓ rejects abbccd
- ✓ rejects abccdd
- ✓ rejects dcba
The 9-state Turing machine accepts by coordinating 4-way symbol matching.
19
Design a Turing machine to recognize the language:
The machine pairs in cycles:
- Replace leftmost with in .
- Find leftmost , replace with in .
- Find leftmost , replace with in .
- Rewind to in .
- In , if is seen, check that all 's and 's are exhausted ().
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q1 | X | R |
| →q0 | Y | q4 | Y | R |
| q1 | Y | q1 | Y | R |
| q1 | 0 | q1 | 0 | R |
| q1 | 1 | q2 | Y | R |
| q2 | Z | q2 | Z | R |
| q2 | 1 | q2 | 1 | R |
| q2 | 2 | q3 | Z | L |
| q3 | Z | q3 | Z | L |
| q3 | 0 | q3 | 0 | L |
| q3 | Y | q3 | Y | L |
| q3 | 1 | q3 | 1 | L |
| q3 | X | q0 | X | R |
| q4 | Y | q4 | Y | R |
| q4 | Z | q5 | Z | R |
| q5 | Z | q5 | Z | R |
| q5 | B | q6 | B | S |
- Machine-checked
- ✓ accepts 012
- ✓ accepts 001122
- ✓ accepts 000111222
- ✓ rejects 01
- ✓ rejects 00122
- ✓ rejects 00112
- ✓ rejects 210
- ✓ rejects 012012
The machine halts in accept state for strings with equal numbers of 's, 's, and 's in order.
20
Design a Turing machine to recognize the language:
- In state :
- If reading , replace with , enter , and scan right.
- If reading , all 's are matched; step into to verify no trailing 's remain.
- In , pass all 's, cross into , skip marked 's, and find the leftmost . Replace with and shift left into .
- In , scan left across 's, cross into , scan left across 's to , and step right back to .
- In , scan across all 's to blank , accepting in .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | c | q5 | c | R |
| q1 | a | q1 | a | R |
| q1 | c | q2 | c | R |
| q2 | Y | q2 | Y | R |
| q2 | b | q3 | Y | L |
| q3 | Y | q3 | Y | L |
| q3 | c | q4 | c | L |
| q4 | a | q4 | a | L |
| q4 | X | q0 | X | R |
| q5 | Y | q5 | Y | R |
| q5 | B | q6 | B | S |
- Machine-checked
- ✓ accepts c
- ✓ accepts acb
- ✓ accepts aacbb
- ✓ accepts aaacbbb
- ✓ rejects ab
- ✓ rejects accb
- ✓ rejects aacb
- ✓ rejects acbb
- ✓ rejects ca
The machine accepts all strings of the form and halts in state .
21
Construct a Turing machine to duplicate an arbitrary string over , transforming .
For each character of , the machine marks it, traverses to the secondary block, appends the replica symbol, and returns to the next unmarked symbol. When all characters are copied, it restores marked symbols back to their original values.
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | b | q2 | Y | R |
| →q0 | B | q7 | B | L |
| q1 | a | q1 | a | R |
| q1 | b | q1 | b | R |
| q1 | B | q3 | B | R |
| q2 | a | q2 | a | R |
| q2 | b | q2 | b | R |
| q2 | B | q4 | B | R |
| q3 | a | q3 | a | R |
| q3 | b | q3 | b | R |
| q3 | B | q5 | a | L |
| q4 | a | q4 | a | R |
| q4 | b | q4 | b | R |
| q4 | B | q5 | b | L |
| q5 | a | q5 | a | L |
| q5 | b | q5 | b | L |
| q5 | B | q6 | B | L |
| q6 | a | q6 | a | L |
| q6 | b | q6 | b | L |
| q6 | X | q0 | X | R |
| q6 | Y | q0 | Y | R |
| q7 | Y | q7 | b | L |
| q7 | X | q7 | a | L |
| q7 | B | h | B | R |
- Machine-checked
- ✓ a → aBa
- ✓ b → bBb
- ✓ ab → abBab
The machine duplicates string into , halting in state .
22
A single-tape Turing machine consists of a sequence of 's and 's. Design a deterministic Turing machine that counts the number of 's: if even, it replaces each by ; if odd, it replaces each by .
- States and track the parity of 's while moving rightward.
- At the trailing blank :
- Even parity branch from : enters leftward rewriting state , which turns every into .
- Odd parity branch from : enters leftward rewriting state , which turns every into .
- When the leading blank is reached, the head steps right and halts in state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 0 | R |
| →q0 | 1 | q1 | 1 | R |
| q1 | 0 | q1 | 0 | R |
| q1 | 1 | q0 | 1 | R |
| →q0 | B | q2 | B | L |
| q1 | B | q3 | B | L |
| q2 | 1 | q2 | 0 | L |
| q2 | 0 | q2 | 0 | L |
| q3 | 0 | q3 | 1 | L |
| q3 | 1 | q3 | 1 | L |
| q2 | B | h | B | R |
| q3 | B | h | B | R |
- Machine-checked
- ✓ 10111 → 00000
- ✓ 11001 → 11111
- ✓ 100 → 111
- ✓ 11 → 00
The machine tests the total count of 1-bits and updates the entire string in accordance with parity, halting in state .
23
Design a Turing machine that takes a binary number as input and computes the 1's complement operation. Test your design on input string .
- State reads bits rightward: converts and .
- Upon reading the trailing blank , enters and moves leftward across all inverted bits without modifying them.
- Upon reaching the leading blank , shifts right into accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 1 | R |
| →q0 | 1 | q0 | 0 | R |
| →q0 | B | q1 | B | L |
| q1 | 0 | q1 | 0 | L |
| q1 | 1 | q1 | 1 | L |
| q1 | B | h | B | R |
- Machine-checked
- ✓ 100 → 011
- ✓ 1011 → 0100
- ✓ 0 → 1
The machine replaces every bit with its binary complement and repositions the head on the leftmost bit in state .
24
Design a single-tape deterministic Turing machine that accepts the language:
The machine tests whether a binary string is a palindrome:
- : Read the leftmost symbol:
- If , replace with and search right in for matching .
- If , replace with and search right in for matching .
- If blank or marked , the string has even length and all symbols matched; accept in .
- : Move right to the trailing blank or marked symbols, shift left, and check the rightmost symbol. If it matches, mark it and return leftward in to .
- If an isolated center character or is detected when the head steps left, the string is an odd palindrome; transition directly to accept state .
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q1 | X | R |
| →q0 | 1 | q4 | Y | R |
| →q0 | X | q6 | X | R |
| →q0 | Y | q6 | Y | R |
| →q0 | B | q6 | B | S |
| q1 | 0 | q1 | 0 | R |
| q1 | 1 | q1 | 1 | R |
| q1 | B | q2 | B | L |
| q1 | X | q2 | X | L |
| q1 | Y | q2 | Y | L |
| q2 | 0 | q3 | X | L |
| q2 | X | q6 | X | R |
| q2 | Y | q6 | Y | R |
| q4 | 0 | q4 | 0 | R |
| q4 | 1 | q4 | 1 | R |
| q4 | B | q5 | B | L |
| q4 | X | q5 | X | L |
| q4 | Y | q5 | Y | L |
| q5 | 1 | q3 | Y | L |
| q5 | X | q6 | X | R |
| q5 | Y | q6 | Y | R |
| q3 | 0 | q3 | 0 | L |
| q3 | 1 | q3 | 1 | L |
| q3 | X | q0 | X | R |
| q3 | Y | q0 | Y | R |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 00
- ✓ accepts 11
- ✓ accepts 010
- ✓ accepts 101
- ✓ accepts 0110
- ✓ accepts 1001
- ✓ rejects 01
- ✓ rejects 10
- ✓ rejects 011
- ✓ rejects 100
- ✓ rejects 0101
The machine accepts all binary palindromes (both odd and even length) and rejects all non-palindromic binary strings.
Exercises
Exercises
How does a Turing machine perform a computing function (i.e. act as a transducer)?
Concept of Turing Machine as a Transducer: A Turing machine can function in two complementary roles:
- Language Recognizer (Acceptor / Decider): Solves a decision problem by halting in an accepting state or rejecting state on input .
- Transducer (Function Computer): Computes an output string from an input argument, evaluating a mathematical function:
The machine is initialized with input string written on consecutive tape cells, surrounded by blank symbols , and the read/write head resting on the leftmost symbol of in start state :
Deterministic Execution and Halting Output: The computation proceeds through a deterministic sequence of transitions according to transition function :
where is a designated halting state and is the final string remaining on the tape when the machine halts.
- Total Computable Function: If is defined for all , the Turing machine is guaranteed to halt for every input with on the tape.
- Partial Computable Function: If is undefined for certain inputs , the machine either enters an infinite loop or halts in a non-accepting/error configuration without writing a valid result.
Concrete Transducer Implementation (Unary Successor Function): In unary representation, integer is encoded as (where ). The successor function maps by scanning to the end of the string and writing an additional .
| 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
- ✓ 1 → 11
- ✓ 11 → 111
- ✓ 111 → 1111
Trace on input ():
The machine halts in state with output () on the tape, successfully computing .
A Turing machine computes a mathematical function by accepting argument inputs placed on its tape in an initial configuration , executing deterministic transitions that rewrite tape squares and move the head, and eventually halting in a designated halting state with the function value remaining on the tape: . If is undefined, the machine fails to halt (enters an infinite loop).
Explain how a Turing machine works in discrete computational steps.
The Atomic Computational Cycle: A Turing machine operates in synchronized, discrete clock cycles governed by its transition function:
At any discrete time step , suppose the machine is in internal state and the read/write head scans a tape cell containing symbol . If , the finite control performs three atomic actions simultaneously:
- State Transition: Updates the internal state from to .
- Tape Writing: Overwrites symbol in the current cell with replacement symbol .
- Head Shift: Shifts the read/write head one cell in direction :
- : moves one cell right.
- : moves one cell left.
- : remains stationary on the current cell.
Step-by-Step Formal Move Semantics (): Let the current tape configuration be , with the head pointing to . In Instantaneous Description (ID) form:
- If , then:
- If where , then:
Each single application of the turnstile operator represents exactly one clock step of the machine. The transitive closure denotes a computation over zero or more discrete steps.
Halting and Non-Termination: The step-by-step computation halts under two conditions:
- Explicit Halting: The machine transitions into a designated halting state .
- Undefined Transition: The machine reaches a configuration for which is not defined.
If a valid transition remains defined for every configuration encountered, the machine executes an infinite loop and never terminates.
At each discrete clock step, the machine inspects its current internal state and the tape symbol currently scanned by its read/write head. Consulting the transition function , the finite control simultaneously:
- Changes its internal state to .
- Overwrites the scanned symbol with symbol .
- Moves the read/write head one cell left (), one cell right (), or leaves it stationary ().
Computation halts when no transition is defined for the current state-symbol pair.
Describe the working of a Turing machine along with a block diagram.
Block Diagram Representation: A standard single-tape Turing machine consists of three interconnected physical subsystems:
+-----------------------------------------------------------------+
| ... | B | a | b | a | b | B | B | ... Infinite Memory Tape |
+-----------------------------------------------------------------+
^
| (Bidirectional Read/Write Head: L, R, S)
v
+-------------------+
| Finite State |
| Control (Q, δ) |
| Current State: q |
+-------------------+
The functional roles of these three blocks are:
- Finite State Control: A finite automaton storing the active control state and executing state changes according to transition table .
- Infinite Tape: A linear sequence of discrete cells, unbounded in extent. Each cell holds exactly one symbol from tape alphabet , with blank symbol filling all unused cells.
- Read/Write Head: A bidirectional physical access head positioned over one cell at any time, capable of scanning the active symbol, rewriting it, and shifting left () or right ().
Formal 7-Tuple Specification: A deterministic Turing machine is formally defined as a 7-tuple:
where:
- is a finite set of internal states.
- is a finite input alphabet ().
- is a finite tape alphabet containing all input symbols plus auxiliary symbols and blank ().
- is the partial transition function.
- is the initial start state.
- is the blank symbol.
- is the set of final (accepting) states.
Execution Workflow:
- Initialization: Input is placed in cells . All other cells hold . Head starts at cell 0 in state .
- Operation: At each step, finite control reads symbol under the head, looks up , changes state to , overwrites with , and shifts head in direction .
- Termination: The machine halts when state is reached (acceptance) or when no transition is defined (rejection).
A Turing machine consists of three interconnected blocks:
- Finite State Control: A finite-state sequential circuit that stores the current internal state and houses the transition logic .
- Infinite Tape: A linear memory medium partitioned into discrete cells, unbounded in extent, each storing a symbol from (with unused cells containing blank ).
- Read/Write Head: A bidirectional access head capable of reading the active cell, rewriting its content, and shifting left or right under the command of the finite control.
How can we represent the configuration (Instantaneous Description) of a Turing machine?
Necessity of the Instantaneous Description: Unlike a finite automaton where the current internal state completely defines its configuration, a Turing machine computation depends on three dynamic properties:
- The current internal state .
- The current contents of all tape cells up to the rightmost non-blank symbol.
- The exact cell currently scanned by the read/write head.
This complete operational snapshot is known as an Instantaneous Description (ID) or configuration.
Standard Mathematical Representation: : An ID is formally written as a single string:
where:
- represents the string on the tape from the leftmost non-blank cell up to (but not including) the currently scanned cell.
- represents the current state of the finite control.
- represents the tape string starting from the currently scanned symbol through to the rightmost non-blank symbol.
The symbol immediately to the right of state in the ID string is always the symbol currently under the read/write head.
Transition Mechanics and Concrete Example: Let be an ID:
- Right Move (): If :
- Left Move (): If :
Sample Computation Trace on with rule and :
The trace records each intermediate state, tape contents, and head location at every step.
The configuration of a Turing machine is represented by an Instantaneous Description (ID) written as , where is the current machine state, is the tape string to the left of the head, and is the tape string starting from the currently scanned symbol to the rightmost non-blank cell. A single transition is denoted by , and a multi-step computation by .