Past exam question: 2082 Chaitra (Regular), Q13
Open in the Padhaiko appQuestion
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:
- 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:
- Encoding Tape Symbols: Let tape symbols be , where , , and (blank). Symbol is encoded as:
- Encoding Directions: Directions are encoded by unary codes:
- Encoding a Single Transition Rule: A transition is represented by separating its 5 components with single
1s:
- Encoding the Complete Machine and Input:
- The entire transition table of is constructed by joining individual transition codes with double
1s:
- The entire transition table of is constructed by joining individual transition codes with double
- Input is encoded as .
- The full tape input to is separated by triple
1s:
- The full tape input to is separated by triple
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 .