CS 110: Elements of Computing. Instructor: Jim Aspnes
Due Friday, November 22nd, 2002, at 5:00pm.
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.
Do problems 37 and 39 from page 492 of Brookshear.
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.)
Basic idea: we'll copy all the ones one at a time, marking each one that has been copied already by changing it to an x and each copy by making it a y. Then at the end we will go back and change all the symbols to ones again.
| Current state | Current symbol | Write | Move | New state |
| START | * | * | Right | GET1 |
| GET1 | 0 | 0 | None | HALT |
| GET1 | 1 | x | Right | DROP1 |
| GET1 | y | 1 | Right | CHANGEY |
| DROP1 | 0 | y | Left | FINDX |
| DROP1 | 1 | 1 | Right | DROP1 |
| DROP1 | y | y | Right | DROP1 |
| FINDX | 1 | 1 | Left | FINDX |
| FINDX | y | y | Left | FINDX |
| FINDX | x | x | Right | GET1 |
| CHANGEY | 0 | 0 | Left | CHANGEX |
| CHANGEY | y | 1 | Right | CHANGEY |
| CHANGEX | 1 | 1 | Left | CHANGEX |
| CHANGEX | x | 1 | Left | CHANGEX |
| CHANGEX | * | * | None | HALT |
Problems (a), (b), and (c) are all in the class P. Problem (d) is not.
Any problem in P is also in NP. A simple example that ``looks nondeterministic'' might be ``Given an integer n, is there some integer k such that n = 2k?'' A simple deterministic algorithm is to divide n by 2 and see if there is a remainder. With a nondeterministic machine, one could instead guess k and verify it by computing 2k.
Fri 20 Dec 2002 16:31:41 EST hw9.solutions.tyx Copyright © 2002 by Jim Aspnes