PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q5(a)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Church–Turing Thesis, Universal TM & the Halting Problem

Question

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:

  1. 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:
  1. Tape Symbols: Let , where , , and (blank). Symbol is encoded as:
  1. Directions: are encoded as unary strings:

Encoding of Transitions and Entire Machine:

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

All past exam questions for Theory of Computation