Past exam question: 2082 Chaitra (Regular), Q11
Open in the Padhaiko appQuestion
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:
- The binary number starts at the initial tape head position and ends at the first blank symbol .
- The TM in state sweeps right across all binary digits ( and ) without altering them until it detects blank .
- Upon reaching , the head shifts Left into state to examine the rightmost digit.
- 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.
- If the digit is
Formal Definition and Automaton Specification: The Turing machine is formally defined as where:
- Start state:
- Blank symbol:
- Accept states:
Transitions:
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | 0 | q0 | 0 | R |
| →q0 | 1 | q0 | 1 | R |
| →q0 | B | q1 | B | L |
| q1 | 1 | q_accept | 1 | S |
- 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:
- Input (Decimal 5, Odd):
Halts in , successfully accepted.
- 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.