FRS 119        Fall 2005      working schedule      reading      assignments

BEYOND SILICON:
The Future(s) of Computers


We all expect computers to get faster and better every few months. Gordon E. Moore proposed, in 1965, that, roughly speaking, silicon chips will double in computing power every year and a half. His prediction is now called ``Moore's Law'', and it has held true with remarkable regularity for the past forty years. But there are good reasons why it cannot continue much beyond 2020. At some point, the transistors on a chip will need to become smaller than atoms, or the heat they generate will cause an explosion, or signals will need to travel faster than light. What then? What will computers be like, and how will they work, twenty, or fifty years into the future?

In this seminar, we will explore the fundamental limits placed on computation by physical laws, and new ways to compute that are now being explored seriously by scientists and engineers. These include computers that exploit the weirdness of quantum mechanics, the tiny size and flexibility of DNA molecules, the speed of light waves, or the direct medical applications of living cells.

Ken Steiglitz
ken@cs.princeton.edu

Schedule:
Wednesday, 1:30-4:20 p.m.

Guest Lecturers:

Dr. Bernard Yurke: DNA implementation of addition, October 12.

Prof. David August: The general area of parallelism, November 9.

Prof. Stephen Lyon: Physical implementation of quantum computing, November 30.

Prof. Ron Weiss: Computation using living cells, December 7.

Topics --- (Presently under construction and continually updated)


DNA: Parallelism in a test tube
    ``(Plenty of) Room at the bottom''
    A hard problem
        Complexity theory: a fast overview
        Two graph problems
        A measure of complexity
        Asymptotics
        A computing machine is a computing machine---For now!
        Back to the two graph problems
        NP-complete problems
    Computing without a ``computer''
    DNA structure and the rules
    The first molecular computation
    Discussion questions

Moore's Law and the Time of Silicon: 1960--2020(?)
    Goldfeld's question
    The supercomputer in 1957
    Moore's Law
    Exponential growth
    Back to Moore's Law
    Discussion questions

Valves
    The Electron
    Edison's Light bulb problems
    Vacuum tubes---thermionic valves
    The abstract valve
    A note on storage
    Other realizations of valves
        Electromechanical relays
        Fluidic valves
        Purely mechanical valves
        Technological dead ends?
    Transistors
    Scalability
    Parallel computation: Limits
    Discussion questions

Logic
    The abstract valve
    Gates
    Boolean Algebra
    De Morgan's law
    Completeness
    Discussion questions

Universality
    Computing with billiard balls
    Computing with the Game of Life
    Cellular automata
    The Turing machine
    Discussion questions

Heat
    Why chips can't be three-dimensional
    Heat: kT
    Maxwell's Demon
    Reversible computing
    The hot-fast/cool-slow tradeoff
    Discussion questions

Quantum Computing
    Photons in wonderland
        Superposition
        Single-particle interference
    Quantum computers are more powerful than classical
    Qubits and bra-ket notation
    Reversible Quantum gates
        The quantum NOT gate
        The quantum Controlled-NOT gate
        The quantum Toffoli gate
    A different kind of parallelism
    Discussion questions

Other computing paradigms
    Living cells
    Light
        Optical computing
        Soliton collisions
    Chemical computing
    Mechanical systems
    Discussion questions