CS 110: Elements of Computing. Instructor: Jim Aspnes

Homework Nine

Due Friday, November 22nd, 2002, at 5:00pm.

Your task

A Turing machine

For this problem you are to design a Turing machine that doubles a number expressed in unary (base 1). The input to the Turing machine is given as a tape that contains a * symbol in the leftmost cell, followed by n 1 symbols in the next n cells, and then 0 symbols in the remaining (infinitely many) cells. The head of the Turing machine starts on top of the * symbol. When the Turing machine halts, the tape should contain the * symbol in its original location, followed by 2n 1 symbols in the next 2n cells, and 0 symbols in all other cells. At the end, you may leave the head of the Turing machine wherever is convenient.

Give a state transition table (similar to Figure 11.3 on page 459 of Brookshear) for this Turing machine.

Hint: you can use additional symbols besides 0, 1, and * if you need to, as long as you only use a fixed number.

P vs NP

Do problems 37 and 39 from page 492 of Brookshear.

Submitting your solutions

Write up an email message containing your full name and the answer to these problems in plain text format (this means no HTML or Microsoft word documents), and send it to aspnes+110-02-9@cs.yale.edu. (Note: this is not the same email address as for previous homework.)