Past exam question: 2081 Chaitra (Regular), Q5(a)
Open in the Padhaiko appQuestion
How encoding is done in Turing Machine? Explain.
Solution
Purpose and Principles of Turing Machine Encoding: To enable a Turing Machine to act on another machine as data (such as in a Universal Turing Machine or for formal proofs of undecidability), any arbitrary TM must be serialized into a finite string over binary alphabet .
Encoding Scheme:
- States: Let . Without loss of generality, let be the start state and be the unique accepting state. State is encoded as a string of zeros:
- Tape Symbols: Let , where , , and (blank). Symbol is encoded as:
- Directions: are encoded as unary strings:
Encoding of Transitions and Entire Machine:
- Encoding a Single Transition: A move specifies:
- Current state
- Input symbol
- Next state
- Written symbol
- Move direction The transition rule is encoded by separating its 5 components with single
1s:
- Encoding the Complete TM: Let be the codes of all valid transitions in . The machine is encoded by joining the transition codes with double
1s:
- Input Separation: When presenting an input string to a Universal TM, the combined code is:
Answer:
TM components are mapped to unary strings for states, symbols, and directions. A transition is encoded as . Rules are separated by 11, and the machine is separated from input by 111.