PadhaikoAll subjects

Turing Machines: Representation, Moves & Computing

Theory of Computation (ENCT 203)

Open in the Padhaiko app

4.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.

Definition

Turing Machine (Formal 7-Tuple Definition)

A deterministic Turing machine is formally defined as a 7-tuple:

where:

(or where stationary move is modeled as a two-step transition).

Physical Components of a Turing Machine

A Turing machine consists of three structural elements:

  1. 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 .
  2. 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 ().
  3. 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

Definition

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:

The step relation denotes a single machine transition:

  1. Right Move: If , then:
  1. Left Move: If and with , then:
  1. 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:


4.4 Computing with a Turing Machine

A Turing machine operates in two principal modes:

  1. 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.
  2. 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

Example 1

1

Design a Turing machine to accept the language of equal 's followed by equal 's:

Trace its execution on the input string .

Algorithm Formulation

The strategy matches the leftmost unmarked with the leftmost unmarked :

  1. 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 .
  2. Replace that with , transition to , and move left across 's and 's until encountering the marker .
  3. Move one cell right of back into state , and repeat the cycle for the next .
  4. 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 .
Transition Specification and State Diagram

Let .

TM: Language an bnTM
TM: Language a^n b^n Y/Y,R Y/Y,L a/a,L Y/Y,R a/a,R a/X,R Y/Y,R b/Y,L X/X,R B/B,S q0 q1 q3 q2 q4
StateReadNext StateWriteMove
→q0aq1XR
→q0Yq3YR
q1Yq1YR
q1aq1aR
q1bq2YL
q2Yq2YL
q2aq2aL
q2Xq0XR
q3Yq3YR
q3Bq4BS
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts aabb
  • ✓ accepts aaabbb
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ba
  • ✓ rejects aab
  • ✓ rejects abb
Trace on Input aabb

The sequence of instantaneous descriptions is:

Answer:

The Turing machine correctly accepts . The configuration halts in accept state on valid strings and fails or hangs on strings not in .

Example 2

2

Design a Turing machine to recognize the non-context-free language:

Matching Algorithm for Three Symbol Blocks
  1. In state , replace the leftmost with and shift right in state .
  2. In state , scan past remaining 's and marked 's to find the leftmost . Replace it with and move right in state .
  3. In state , scan past remaining 's and marked 's to find the leftmost . Replace it with and move left in state .
  4. In state , traverse leftward past all 's, 's, 's, 's, and 's until reaching . Move one cell right back into state .
  5. 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 Machine Construction
TM: Language an bn cnTM
TM: Language a^n b^n c^n Z/Z,R Y/Y,R Z/Z,L a/a,L Y/Y,L b/b,L Z/Z,R b/b,R Y/Y,R a/a,R a/X,R Y/Y,R b/Y,R c/Z,L X/X,R Z/Z,R B/B,S q0 q1 q4 q2 q3 q5 q6
StateReadNext StateWriteMove
→q0aq1XR
→q0Yq4YR
q1Yq1YR
q1aq1aR
q1bq2YR
q2Zq2ZR
q2bq2bR
q2cq3ZL
q3Zq3ZL
q3aq3aL
q3Yq3YL
q3bq3bL
q3Xq0XR
q4Yq4YR
q4Zq5ZR
q5Zq5ZR
q5Bq6BS
  • Machine-checked
  • ✓ accepts abc
  • ✓ accepts aabbcc
  • ✓ accepts aaabbbccc
  • ✓ rejects ab
  • ✓ rejects abcde
  • ✓ rejects aabbc
  • ✓ rejects aabcc
  • ✓ rejects cba
Answer:

The 7-state Turing machine accepts by sequentially marking corresponding triples and halting in state .

Example 3

3

Design a Turing machine as a transducer to compute the 1's complement of an arbitrary binary string (e.g. ).

Transducer Inversion Strategy
  1. In state , read each bit from left to right: replace with , and replace with .
  2. Upon reaching the right-hand blank , transition to state and scan leftwards across the inverted bits.
  3. 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.
Machine Transition Specification
TM: 1s Complement TransducerTM
TM: 1s Complement Transducer 0/0,L 1/1,L 0/1,R 1/0,R B/B,L B/B,R q0 q1 q2
StateReadNext StateWriteMove
→q00q01R
→q01q00R
→q0Bq1BL
q10q10L
q11q11L
q1Bq2BR
  • Machine-checked
  • ✓ 1011 → 0100
  • ✓ 1100 → 0011
  • ✓ 0 → 1
  • ✓ 1 → 0
Answer:

The machine inverts every binary bit and restores the head to the starting position in state , correctly outputting the 1's complement.

Example 4

4

Design a Turing machine to compute the 2's complement of any binary string (e.g. , ).

2's Complement Algorithm

By binary arithmetic, the 2's complement of a binary number is obtained by scanning from right to left:

  1. Leave all trailing 's unchanged.
  2. Leave the least significant unchanged.
  3. 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 .
Automaton Definition
TM: 2s ComplementTM
TM: 2s Complement 1/0,L 0/1,L 0/0,L 1/1,R 0/0,R B/B,L 1/1,L B/B,R q0 q1 q2 q3
StateReadNext StateWriteMove
→q01q01R
→q00q00R
→q0Bq1BL
q10q10L
q11q21L
q21q20L
q20q21L
q2Bq3BR
  • Machine-checked
  • ✓ 1011 → 0101
  • ✓ 1100 → 0100
  • ✓ 10 → 10
  • ✓ 1 → 1
Answer:

The Turing machine computes the exact 2's complement representation in state .

Example 5

5

Design a Turing machine to accept the language of even-length palindromes:

Matching Outer Symbols
  1. 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 .
  2. 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 .
  3. 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 .
  4. State travels all the way left until hitting marker , steps right, and returns to .
Automaton Specification
TM: Even Palindrome wwRTM
TM: Even Palindrome ww^R a/a,R b/b,R a/a,L b/b,L a/a,R b/b,R a/X,R b/X,R X/X,R B/B,L X/X,L a/X,L X/X,R X/X,L B/B,L b/X,L q0 q1 q4 q6 q2 q3 q5
StateReadNext StateWriteMove
→q0aq1XR
→q0bq4XR
→q0Xq6XR
q1aq1aR
q1bq1bR
q1Bq2BL
q1Xq2XL
q2aq3XL
q3aq3aL
q3bq3bL
q3Xq0XR
q4aq4aR
q4bq4bR
q4Xq5XL
q4Bq5BL
q5bq3XL
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts abba
  • ✓ accepts baab
  • ✓ accepts aabbaa
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aba
  • ✓ rejects aab
  • ✓ rejects bab
Answer:

The machine matches outer pairs inward and halts in accepting state if and only if the input is an even-length palindrome.

Example 6

6

Design a Turing machine to accept the language of odd-length palindromes over :

Odd Palindrome Matching Mechanism

The machine pairs outer symbols inward:

  1. In state , read the leftmost symbol:
    • If , mark with and move right into .
    • If , mark with and move right into .
  2. In (or ), scan rightward to the right end of the unexamined string (marked by blank or previous marker ), shift left into (or ).
  3. 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 .
  4. Similarly in (expecting ), if it reads , mark with and return leftward in ; if it reads , accept directly in .
  5. In state , scan left to the leftmost marker , step right, and repeat from .
Automaton Spec
TM: Odd Palindrome wcwRTM
TM: Odd Palindrome wcw^R a/a,R b/b,R a/a,L b/b,L a/a,R b/b,R a/X,R b/X,R B/B,L X/X,L a/X,L X/X,R X/X,R X/X,L B/B,L b/X,L X/X,R q0 q1 q4 q2 q3 q6 q5
StateReadNext StateWriteMove
→q0aq1XR
→q0bq4XR
q1aq1aR
q1bq1bR
q1Bq2BL
q1Xq2XL
q2aq3XL
q2Xq6XR
q3aq3aL
q3bq3bL
q3Xq0XR
q4aq4aR
q4bq4bR
q4Xq5XL
q4Bq5BL
q5bq3XL
q5Xq6XR
  • 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
Answer:

The machine verifies symmetrical outer characters surrounding the isolated middle symbol and halts in state .

Example 7

7

Design a Turing machine that increments an arbitrary binary string by 1 (i.e. computes ).

Binary Addition Logic

Adding 1 to a binary integer:

  1. : Move right across all digits to locate the least significant bit adjacent to blank .
  2. : 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 .
  3. : Move right to the trailing blank and step left into accept state .
Automaton Definition
TM: Binary Increment by 1TM
TM: Binary Increment by 1 1/1,R 0/0,R 1/0,L 1/1,R 0/0,R B/B,L 0/1,R B/1,R B/B,L q0 q1 q2 q3
StateReadNext StateWriteMove
→q01q01R
→q00q00R
→q0Bq1BL
q11q10L
q10q21R
q1Bq21R
q21q21R
q20q20R
q2Bq3BL
  • Machine-checked
  • ✓ 0 → 1
  • ✓ 101 → 110
  • ✓ 111 → 1000
  • ✓ 1011 → 1100
Answer:

The machine handles all carry propagation (including length expansion such as ) and halts in state .

Example 8

8

Design a Turing machine to accept the language of arbitrary palindromes (even or odd length):

Unified Palindrome Checking Strategy

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.
Automaton Definition
TM: General Palindrome AcceptorTM
TM: General Palindrome Acceptor a/a,R b/b,R a/a,L b/b,L a/a,R b/b,R a/X,R b/X,R X/X,R B/B,L X/X,L a/X,L X/X,R X/X,R X/X,L B/B,L b/X,L X/X,R q0 q1 q4 q6 q2 q3 q7 q5
StateReadNext StateWriteMove
→q0aq1XR
→q0bq4XR
→q0Xq6XR
q1aq1aR
q1bq1bR
q1Bq2BL
q1Xq2XL
q2aq3XL
q2Xq7XR
q3aq3aL
q3bq3bL
q3Xq0XR
q4aq4aR
q4bq4bR
q4Xq5XL
q4Bq5BL
q5bq3XL
q5Xq7XR
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts aba
  • ✓ accepts bab
  • ✓ accepts abba
  • ✓ accepts baab
  • ✓ accepts ababa
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects aab
  • ✓ rejects abb
Answer:

The machine accepts both even- and odd-length palindromic strings over .

Example 9

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.

Parity Analysis

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.

Automaton Specification
TM: LSB Parity ModifierTM
TM: LSB Parity Modifier 0/0,R 1/1,R B/B,L 1/0,S 0/1,S q0 q1 h
StateReadNext StateWriteMove
→q00q00R
→q01q01R
→q0Bq1BL
q11h0S
q10h1S
  • Machine-checked
  • ✓ 101 → 100
  • ✓ 100 → 101
  • ✓ 1110 → 1111
  • ✓ 1111 → 1110
Answer:

The machine scans to the end of the binary string, inverts the least significant bit in state , and halts immediately in state .

Example 10

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 .

Parity Accumulator and Rewriting
  1. State represents an even parity of 's seen so far; represents odd parity.
  2. The machine scans rightward:
    • In : reading stays in ; reading flips to .
    • In : reading stays in ; reading flips to .
  3. 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 .
  4. Reaching the leading blank transitions into halt state .
State Machine Construction
TM: Parity-Based Bit TransformerTM
TM: Parity-Based Bit Transformer 0/1,L 1/1,L 1/0,L 0/0,L 0/0,R 0/0,R 1/1,R 1/1,R B/B,L B/B,L B/B,R B/B,R q0 q1 q2 q3 h
StateReadNext StateWriteMove
→q00q00R
→q01q11R
q10q10R
q11q01R
→q0Bq2BL
q1Bq3BL
q21q20L
q20q20L
q30q31L
q31q31L
q2BhBR
q3BhBR
  • Machine-checked
  • ✓ 10111 → 00000
  • ✓ 11001 → 11111
  • ✓ 000 → 000
  • ✓ 11 → 00
Answer:

The machine correctly tests the parity of 1-bits and transforms the entire tape according to the problem specification.

Example 11

11

Design a Turing machine to recognize all strings of even length over the alphabet .

Even Length Modulo Counter

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.
Automaton Definition
TM: Even Length String RecognizerTM
TM: Even Length String Recognizer a/a,R b/b,R a/a,R b/b,R B/B,S q0 q1 h
StateReadNext StateWriteMove
→q0aq1aR
→q0bq1bR
q1aq0aR
q1bq0bR
→q0BhBS
  • 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
Answer:

The machine accepts all strings with and rejects all odd-length strings.

Example 12

12

Design a Turing machine to copy an arbitrary string over , transforming .

String Copying Algorithm

To duplicate string :

  1. 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 .
  2. State moves past the original string and the separating blank to deposit an at the end of the duplicate.
  3. State moves past the original string and the separating blank to deposit a at the end of the duplicate.
  4. States scan leftward across both copies to return to the marker in , step right, and repeat.
State Machine Construction
TM: String DuplicatorTM
TM: String Duplicator Y/b,L X/a,L a/a,L b/b,L a/a,L b/b,L a/a,R b/b,R a/a,R b/b,R a/a,R b/b,R a/a,R b/b,R a/X,R b/Y,R B/B,L B/B,R B/B,R B/a,L B/b,L B/B,L X/X,R Y/Y,R B/B,R q0 q1 q2 q7 q3 q4 q5 q6 h
StateReadNext StateWriteMove
→q0aq1XR
→q0bq2YR
→q0Bq7BL
q1aq1aR
q1bq1bR
q1Bq3BR
q2aq2aR
q2bq2bR
q2Bq4BR
q3aq3aR
q3bq3bR
q3Bq5aL
q4aq4aR
q4bq4bR
q4Bq5bL
q5aq5aL
q5bq5bL
q5Bq6BL
q6aq6aL
q6bq6bL
q6Xq0XR
q6Yq0YR
q7Yq7bL
q7Xq7aL
q7BhBR
  • Machine-checked
  • ✓ a → aBa
  • ✓ b → bBb
  • ✓ ab → abBab
Answer:

The machine duplicates string separated by blank , leaving the tape in configuration and halting in state .

Example 13

13

Design a Turing machine to compute the arithmetic doubling function using unary representation ( represented by ones).

Doubling Strategy in Unary

For each in the input, the machine appends two 's at the end of the output area:

  1. State replaces the leftmost of with and enters . If it reads blank , all inputs are processed, entering .
  2. In , the head moves past the separating blank to the end of the copied block, appends a in and another in .
  3. States return the head leftward to the marker , move right, and repeat from .
  4. In state , the machine clears all temporary markers, converting them to blanks so that only the doubled ones remain on the tape.
State Machine Construction
TM: Unary Doubling f(x)=2xTM
TM: Unary Doubling f(x)=2x X/B,L 1/1,L 1/1,L 1/1,R 1/1,R 1/X,R B/B,L B/B,R B/1,R B/1,L B/B,L X/X,R B/B,L q0 q1 q6 q2 q3 q4 q5 qh
StateReadNext StateWriteMove
→q01q1XR
→q0Bq6BL
q11q11R
q1Bq2BR
q21q21R
q2Bq31R
q3Bq41L
q41q41L
q4Bq5BL
q51q51L
q5Xq0XR
q6Xq6BL
q6BqhBL
  • Machine-checked
  • ✓ 1 → 11
  • ✓ 11 → 1111
  • ✓ 111 → 111111
Answer:

The Turing machine computes , producing tally marks for any input of tally marks.

Example 14

14

Design a Turing machine to compute the successor-by-two function for in unary representation ( represented by ).

Appending Two Tallies

To compute :

  1. In state , scan rightward across the tally marks ().
  2. Upon reaching the terminating blank , write , step right, and enter .
  3. In state , write another , step stationary (), and enter accept state .
Automaton Definition
TM: Unary f(x)=x+2TM
TM: Unary f(x)=x+2 1/1,R B/1,R B/1,S q0 q1 q2
StateReadNext StateWriteMove
→q01q01R
→q0Bq11R
q1Bq21S
  • Machine-checked
  • ✓ 1 → 111
  • ✓ 11 → 1111
  • ✓ 111 → 11111
Answer:

The machine appends two 's to the right of the input block, correctly computing .

Example 15

15

Design a Turing machine to compute unary addition:

where the inputs and are presented as .

Unary Addition by Blank Replacement

Two unary numbers separated by a single blank can be added in steps:

  1. In state , scan rightward across the first block of ones ().
  2. When the separator blank is reached, replace it with and enter . The tape now contains ones.
  3. In , move right to the end of the second block until encountering blank . Step left into .
  4. In , erase the surplus by replacing it with blank , and halt in state .
Automaton Specification
TM: Unary Addition f(m,n)=m+nTM
TM: Unary Addition f(m,n)=m+n 1/1,R 1/1,R B/1,R B/B,L 1/B,S q0 q1 q2 h
StateReadNext StateWriteMove
→q01q01R
→q0Bq11R
q11q11R
q1Bq2BL
q21hBS
  • Machine-checked
  • ✓ 1B1 → 11
  • ✓ 11B111 → 11111
  • ✓ 111B11 → 11111
Answer:

The machine fills the internal blank and removes one boundary tally, leaving exactly consecutive ones on the tape.

Example 16

16

Design a Turing machine to compute the projection function in unary notation ().

Erasing the First Argument
  1. In state , erase the first argument by replacing each with blank ().
  2. When the separating blank is reached, step right into .
  3. In state , scan rightward across the remaining tallies ().
  4. Reaching the trailing blank halts in state , leaving only the tallies on the tape.
Automaton Definition
TM: Projection Function f(x,y)=yTM
TM: Projection Function f(x,y)=y 1/1,R 1/B,R B/B,R B/B,S q0 q1 h
StateReadNext StateWriteMove
→q01q0BR
→q0Bq1BR
q11q11R
q1BhBS
  • Machine-checked
  • ✓ 1B1 → 1
  • ✓ 111B11 → 11
  • ✓ 11B1111 → 1111
Answer:

The machine erases the initial block of ones, leaving the second argument intact on the tape.

Example 17

17

Design a Turing machine to compute the multiplication function in unary representation.

Multiplication as Repeated Addition

Given input :

  1. For each of the tallies in the first argument, make a complete copy of the tallies at the end of the tape.
  2. Maintain loop counters using tape markers: overwrite one of with , then iterate over each of , marking it and writing a into the product zone.
  3. Once all are copied, restore and repeat for the next of .
  4. When is exhausted, clean up markers and halt.
State Machine Construction
TM: Unary Multiplication f(x,y)=x*yTM
TM: Unary Multiplication f(x,y)=x*y 1/B,R 1/1,L X/1,L 1/1,L 1/1,L 1/1,R 1/1,R 1/1,R 1/B,R B/B,R B/B,R 1/X,R B/B,L B/B,R B/1,L B/B,L X/X,R B/B,L B/B,R B/B,R q0 q1 q9 q2 q3 q7 q4 q5 q6 q8 h
StateReadNext StateWriteMove
→q01q1BR
→q0Bq9BR
q11q11R
q1Bq2BR
q21q3XR
q2Bq7BL
q31q31R
q3Bq4BR
q41q41R
q4Bq51L
q51q51L
q5Bq6BL
q61q61L
q6Xq2XR
q7Xq71L
q7Bq8BL
q81q81L
q8Bq0BR
q91q9BR
q9BhBR
  • Machine-checked
  • ✓ 1B1 → 1
  • ✓ 11B11 → 1111
  • ✓ 11B111 → 111111
Answer:

The Turing machine computes , producing tallies for inputs and .

Example 18

18

Design a Turing machine to accept the language:

Four-Symbol Cross-Checking Algorithm
  1. In state , replace the leftmost with and move right into .
  2. In , skip 's and marked 's to find the leftmost ; mark it and enter .
  3. In , skip 's and marked 's to find the leftmost ; mark it and enter .
  4. In , skip 's and marked 's to find the leftmost ; mark it and enter .
  5. In , move all the way left past until reaching marker . Step right into to begin the next pass.
  6. When sees marker (no more 's), states verify that all 's, 's, and 's have been consumed, halting in accept state .
Automaton Definition
TM: Language an bn cn dnTM
TM: Language a^n b^n c^n d^n Z/Z,R Y/Y,R X/X,R Z/Z,L a/a,L X/X,L b/b,L Y/Y,L c/c,L Z/Z,R c/c,R b/b,R Y/Y,R X/X,R a/a,R a/W,R X/X,R b/X,R c/Y,R d/Z,L W/W,R Y/Y,R Z/Z,R B/B,S q0 q1 q5 q2 q3 q4 q6 q7 q8
StateReadNext StateWriteMove
→q0aq1WR
→q0Xq5XR
q1Xq1XR
q1aq1aR
q1bq2XR
q2bq2bR
q2Yq2YR
q2cq3YR
q3Zq3ZR
q3cq3cR
q3dq4ZL
q4Zq4ZL
q4aq4aL
q4Xq4XL
q4bq4bL
q4Yq4YL
q4cq4cL
q4Wq0WR
q5Xq5XR
q5Yq6YR
q6Yq6YR
q6Zq7ZR
q7Zq7ZR
q7Bq8BS
  • Machine-checked
  • ✓ accepts abcd
  • ✓ accepts aabbccdd
  • ✓ accepts aaabbbcccddd
  • ✓ rejects abc
  • ✓ rejects aabcdd
  • ✓ rejects abbccd
  • ✓ rejects abccdd
  • ✓ rejects dcba
Answer:

The 9-state Turing machine accepts by coordinating 4-way symbol matching.

Example 19

19

Design a Turing machine to recognize the language:

Ternary Equal Blocks Matching

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 ().
Automaton Definition
TM: Language 0n 1n 2nTM
TM: Language 0^n 1^n 2^n Z/Z,R Y/Y,R Z/Z,L 0/0,L Y/Y,L 1/1,L Z/Z,R 1/1,R Y/Y,R 0/0,R 0/X,R Y/Y,R 1/Y,R 2/Z,L X/X,R Z/Z,R B/B,S q0 q1 q4 q2 q3 q5 q6
StateReadNext StateWriteMove
→q00q1XR
→q0Yq4YR
q1Yq1YR
q10q10R
q11q2YR
q2Zq2ZR
q21q21R
q22q3ZL
q3Zq3ZL
q30q30L
q3Yq3YL
q31q31L
q3Xq0XR
q4Yq4YR
q4Zq5ZR
q5Zq5ZR
q5Bq6BS
  • Machine-checked
  • ✓ accepts 012
  • ✓ accepts 001122
  • ✓ accepts 000111222
  • ✓ rejects 01
  • ✓ rejects 00122
  • ✓ rejects 00112
  • ✓ rejects 210
  • ✓ rejects 012012
Answer:

The machine halts in accept state for strings with equal numbers of 's, 's, and 's in order.

Example 20

20

Design a Turing machine to recognize the language:

Matching a's and b's Across Central Marker c
  1. In state :
    • If reading , replace with , enter , and scan right.
    • If reading , all 's are matched; step into to verify no trailing 's remain.
  2. In , pass all 's, cross into , skip marked 's, and find the leftmost . Replace with and shift left into .
  3. In , scan left across 's, cross into , scan left across 's to , and step right back to .
  4. In , scan across all 's to blank , accepting in .
Automaton Specification
TM: Language an c bnTM
TM: Language a^n c b^n Y/Y,R a/a,L Y/Y,L Y/Y,R a/a,R a/X,R c/c,R c/c,R b/Y,L c/c,L X/X,R B/B,S q0 q1 q5 q2 q3 q4 q6
StateReadNext StateWriteMove
→q0aq1XR
→q0cq5cR
q1aq1aR
q1cq2cR
q2Yq2YR
q2bq3YL
q3Yq3YL
q3cq4cL
q4aq4aL
q4Xq0XR
q5Yq5YR
q5Bq6BS
  • Machine-checked
  • ✓ accepts c
  • ✓ accepts acb
  • ✓ accepts aacbb
  • ✓ accepts aaacbbb
  • ✓ rejects ab
  • ✓ rejects accb
  • ✓ rejects aacb
  • ✓ rejects acbb
  • ✓ rejects ca
Answer:

The machine accepts all strings of the form and halts in state .

Example 21

21

Construct a Turing machine to duplicate an arbitrary string over , transforming .

Two-Pass Symbol Replication

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.

Automaton Specification
TM: String CopierTM
TM: String Copier Y/b,L X/a,L a/a,L b/b,L a/a,L b/b,L a/a,R b/b,R a/a,R b/b,R a/a,R b/b,R a/a,R b/b,R a/X,R b/Y,R B/B,L B/B,R B/B,R B/a,L B/b,L B/B,L X/X,R Y/Y,R B/B,R q0 q1 q2 q7 q3 q4 q5 q6 h
StateReadNext StateWriteMove
→q0aq1XR
→q0bq2YR
→q0Bq7BL
q1aq1aR
q1bq1bR
q1Bq3BR
q2aq2aR
q2bq2bR
q2Bq4BR
q3aq3aR
q3bq3bR
q3Bq5aL
q4aq4aR
q4bq4bR
q4Bq5bL
q5aq5aL
q5bq5bL
q5Bq6BL
q6aq6aL
q6bq6bL
q6Xq0XR
q6Yq0YR
q7Yq7bL
q7Xq7aL
q7BhBR
  • Machine-checked
  • ✓ a → aBa
  • ✓ b → bBb
  • ✓ ab → abBab
Answer:

The machine duplicates string into , halting in state .

Example 22

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 .

Parity Branching Algorithm
  1. States and track the parity of 's while moving rightward.
  2. 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 .
  3. When the leading blank is reached, the head steps right and halts in state .
Machine Transition Diagram
TM: Binary Parity InverterTM
TM: Binary Parity Inverter 0/1,L 1/1,L 1/0,L 0/0,L 0/0,R 0/0,R 1/1,R 1/1,R B/B,L B/B,L B/B,R B/B,R q0 q1 q2 q3 h
StateReadNext StateWriteMove
→q00q00R
→q01q11R
q10q10R
q11q01R
→q0Bq2BL
q1Bq3BL
q21q20L
q20q20L
q30q31L
q31q31L
q2BhBR
q3BhBR
  • Machine-checked
  • ✓ 10111 → 00000
  • ✓ 11001 → 11111
  • ✓ 100 → 111
  • ✓ 11 → 00
Answer:

The machine tests the total count of 1-bits and updates the entire string in accordance with parity, halting in state .

Example 23

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 .

Bit Inversion and Rewind
  1. State reads bits rightward: converts and .
  2. Upon reading the trailing blank , enters and moves leftward across all inverted bits without modifying them.
  3. Upon reaching the leading blank , shifts right into accept state .
Automaton Definition
TM: 1s Complement TesterTM
TM: 1s Complement Tester 0/0,L 1/1,L 0/1,R 1/0,R B/B,L B/B,R q0 q1 h
StateReadNext StateWriteMove
→q00q01R
→q01q00R
→q0Bq1BL
q10q10L
q11q11L
q1BhBR
  • Machine-checked
  • ✓ 100 → 011
  • ✓ 1011 → 0100
  • ✓ 0 → 1
Answer:

The machine replaces every bit with its binary complement and repositions the head on the leftmost bit in state .

Example 24

24

Design a single-tape deterministic Turing machine that accepts the language:

Binary Palindrome Strategy

The machine tests whether a binary string is a palindrome:

  1. : 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 .
  2. : 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 .
  3. If an isolated center character or is detected when the head steps left, the string is an odd palindrome; transition directly to accept state .
Automaton Definition
TM: Binary Palindrome wcwRTM
TM: Binary Palindrome wcw^R 0/0,L 1/1,L 0/0,R 1/1,R 0/0,R 1/1,R 0/X,R 1/Y,R X/X,R Y/Y,R B/B,S B/B,L X/X,L Y/Y,L 0/X,L X/X,R Y/Y,R B/B,L X/X,L Y/Y,L 1/Y,L X/X,R Y/Y,R X/X,R Y/Y,R q0 q1 q4 q6 q2 q3 q5
StateReadNext StateWriteMove
→q00q1XR
→q01q4YR
→q0Xq6XR
→q0Yq6YR
→q0Bq6BS
q10q10R
q11q11R
q1Bq2BL
q1Xq2XL
q1Yq2YL
q20q3XL
q2Xq6XR
q2Yq6YR
q40q40R
q41q41R
q4Bq5BL
q4Xq5XL
q4Yq5YL
q51q3YL
q5Xq6XR
q5Yq6YR
q30q30L
q31q31L
q3Xq0XR
q3Yq0YR
  • 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
Answer:

The machine accepts all binary palindromes (both odd and even length) and rejects all non-palindromic binary strings.


Exercises

Exercises

Question 1

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:

  1. Language Recognizer (Acceptor / Decider): Solves a decision problem by halting in an accepting state or rejecting state on input .
  2. 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 .

TM Transducer: Unary Successor S(x) = x + 1TM
TM Transducer: Unary Successor S(x) = x + 1 1/1,R B/1,S q0 h
StateReadNext StateWriteMove
→q01q01R
→q0Bh1S
  • 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 .

Answer:

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).

Question 2

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:

  1. State Transition: Updates the internal state from to .
  2. Tape Writing: Overwrites symbol in the current cell with replacement symbol .
  3. 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:

  1. Explicit Halting: The machine transitions into a designated halting state .
  2. 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.

Answer:

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:

  1. Changes its internal state to .
  2. Overwrites the scanned symbol with symbol .
  3. 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.

Question 3

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:

  1. Finite State Control: A finite automaton storing the active control state and executing state changes according to transition table .
  2. 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.
  3. 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:

  1. Initialization: Input is placed in cells . All other cells hold . Head starts at cell 0 in state .
  2. Operation: At each step, finite control reads symbol under the head, looks up , changes state to , overwrites with , and shifts head in direction .
  3. Termination: The machine halts when state is reached (acceptance) or when no transition is defined (rejection).
Answer:

A Turing machine consists of three interconnected blocks:

  1. Finite State Control: A finite-state sequential circuit that stores the current internal state and houses the transition logic .
  2. Infinite Tape: A linear memory medium partitioned into discrete cells, unbounded in extent, each storing a symbol from (with unused cells containing blank ).
  3. 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.
Question 4

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:

  1. The current internal state .
  2. The current contents of all tape cells up to the rightmost non-blank symbol.
  3. 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:

  1. Right Move (): If :
  1. Left Move (): If :

Sample Computation Trace on with rule and :

The trace records each intermediate state, tape contents, and head location at every step.

Answer:

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 .

Past exam questions for Theory of Computation

← Pushdown Automata, CFG↔PDA & Context-Sensitive GrammarTM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions →