PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q11

Theory of Computation · 5 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

Design a Turing machine that accepts the language of odd number written in binary.

Solution

Mathematical Characterization and Operational Logic: A non-negative integer represented in standard binary () is odd if and only if its least significant bit (the rightmost bit) is 1.

Tape Format & Strategy:

  1. The binary number starts at the initial tape head position and ends at the first blank symbol .
  2. The TM in state sweeps right across all binary digits ( and ) without altering them until it detects blank .
  3. Upon reaching , the head shifts Left into state to examine the rightmost digit.
  4. In state :
    • If the digit is 1, the number is odd: transition to accepting state .
    • If the digit is 0, the number is even: halt without accepting (or transition to a reject state).
    • If the tape cell is blank (empty string ), reject.

Formal Definition and Automaton Specification: The Turing machine is formally defined as where:

Transitions:

TM: Odd Binary NumbersTM
TM: Odd Binary Numbers 0/0,R 1/1,R B/B,L 1/1,S q0 q1 q_accept
StateReadNext StateWriteMove
→q00q00R
→q01q01R
→q0Bq1BL
q11q_accept1S
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 11
  • ✓ accepts 101
  • ✓ accepts 111
  • ✓ accepts 1001
  • ✓ accepts 01
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 10
  • ✓ rejects 100
  • ✓ rejects 110
  • ✓ rejects 000

Trace on Example Inputs:

  1. Input (Decimal 5, Odd):

Halts in , successfully accepted.

  1. Input (Decimal 6, Even):

In , reading has no transition to , so the machine halts and rejects.

Answer:

The TM scans rightward to the blank symbol, moves one step left to inspect the least significant bit, and accepts in state if and only if that bit is 1.

All past exam questions for Theory of Computation