PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q13

Theory of Computation · 3 marks

Open in the Padhaiko app

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

Question

Explain the encoding process of Universal Turing Machine.

Solution

Concept of Universal Turing Machine (UTM): A Universal Turing Machine (UTM) is a single reprogrammable Turing Machine that can simulate any arbitrary Turing machine operating on any input string . It takes as input an encoded description of and on its tape:

To enable to parse and execute , all components of are systematically mapped to binary strings over .

Standard Binary Encoding Scheme:

  1. Encoding States: Let states be , where is always the start state and is the unique accepting state. State is encoded as a unary string of zeros:
  1. Encoding Tape Symbols: Let tape symbols be , where , , and (blank). Symbol is encoded as:
  1. Encoding Directions: Directions are encoded by unary codes:
  1. Encoding a Single Transition Rule: A transition is represented by separating its 5 components with single 1s:
  1. Encoding the Complete Machine and Input:
    • The entire transition table of is constructed by joining individual transition codes with double 1s:
Answer:

The UTM encodes states , symbols , and directions as unary zeros . Each transition is encoded as , transitions are separated by , and the machine description is separated from input by .

All past exam questions for Theory of Computation