4. 3 x 10 30 points A (normal) enumerator is a version of a Turing machine M tha

Question

4. 3 x 10 30 points A (normal) enumerator is a version of a Turing machine M that has an extra output tape or a printer attached, as the textbook formulates it Both tapes are completely blank as the machine starts. M writes a sequence of strings onto the output tape with a separation symbol (e.g a comma) between them. This sequence is finite or infinite. Repetitions of strings are allowed. The generated language is the set of all the listed strings A lexicographic enumerator is an enumerator that writes its list in shortlex order (ordered by length first, and ordered lexicographically for each fixed length).

Explanation / Answer

The idea of the machine is reframe the problem as purely textual. It needs to replace the +with a * and then change the last * to _.

This process just has four states. In the first one, we skip over the first number (because the Turing machine has to write every transition, it just writes what it read). We’ve reached the end of the first number when we see +, so we write * and then go to the next state. In the second state, we skip over the second number. We know we’ve reached the end of when we see _, but the number is one * too long, so, we go back one * and replace it with _. Then, we go back to the beginning, skipping over the *s.

This process takes 15 steps to perform the addition 2 + 3. The trace looks like this:

consume-first-number :  [*]*+***  { 0}

consume-first-number :  *[*]+***  { 1}

consume-first-number :  **[+]***  { 2}

consume-second-number:  ***[*]**  { 3}

consume-second-number:  ****[*]*  { 4}

consume-second-number:  *****[*]  { 5}

consume-second-number:  ******[_] { 6}

override-last-*      :  *****[*]_ { 7}

seek-beginning       :  ****[*]__ { 8}

seek-beginning       :  ***[*]*__ { 9}

seek-beginning       :  **[*]**__ {10}

seek-beginning       :  *[*]***__ {11}

seek-beginning       :  [*]****__ {12}

seek-beginning       : [_]*****__ {13}

HALT                 : _[*]****__ {14}

We don’t really need to go back to the beginning, but it seems polite to and it makes the programs a little harder to write.

Something that is very important to understand about this machine is that the symbol +has no meaning. The Turing machine is not interpreting one arithmetic operation out of many possible operations it can perform. The + is just an arbitrary delimiter between the two numbers.

(define implicit-unary-addition   (implicit-tm    [consume-first-number     [* (consume-first-number * R)]     [+ (consume-second-number * R)]]    [consume-second-number     [* (consume-second-number * R)]     [_ (override-last-* _ L)]]    [override-last-*     [* (seek-beginning _ L)]]    [seek-beginning     [* (seek-beginning * L)]     [_ (HALT _ R)]]))

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.