Assignment 6, due Nov. 16, 2005

Read:

E. Fredkin and T. Toffoli, "Conservative logic", Int. J. of Theor. Phys., vol. 21, pp. 219-253, 1982 (posted in the usual place).

---

Problems:

1. Show how to implement the switch gate (Fig. 16) using standard AND, NOT, OR gates.

2. Show how to implement the Fredkin gate (Fig. 2) using standard AND, NOT, OR gates.

3. Fredkin and Toffoli leave open their Question 4, Section 5, which I'll paraphrase as ``Can reversible computing work in the real world, where there's noise?'' Discuss this question if the billiard-ball model of computation is used.

4. Describe, briefly, in a paragraph or two, the main points in Prof. August's guest lecture, and what they imply about the future of the transistor-based silicon chip and Moore's Law.

---

Extra Credit

Set up the billiard-ball model in Fredkin and Toffoli 82 as a two-dimensional cellular automaton. Describe the cell space, set of possible states at each cell, neighborhood of each cell, initial conditions, and the state transition rule. Don't forget mirrors. Don't forget to reference all your sources!

Note that Fredkin and Toffoli restrict attention to collisions of balls at right angles, so you should also. Furthermore, you can assume, for simplicity, that balls always have a positive left-to-right velocity component, so that they are always traveling either up to the right or down to the right. (Does this assumption destroy universality?)

Mucho Extra Credit, or maybe a term paper

For those of you with substantial programming experience and no life: implement the cellular automaton you proposed for Fredkin and Toffoli's billiard-ball computer. A nice display window and an interface that allows the user to set up gates and run a simulation would make this a professional job, one that could be posted for the world to play with. (I looked quickly and didn't find a site like this. Please let me know if you find one.)

---