CSE599 Syllabus

Catalog Data

CSE 599 Alternative Computing Paradigms (4): Examines the future of computers. Considers IC technology: How it drives computer design, and what the fundamental limitations are. Examines the proposed alternatives, including neurobiologically inspired computing, DNA computing, and quantum computing.
 

Introduction

For the past 20 years, the throughput of digital computers has increased at an exponential rate. Fueled by (seemingly endless) improvements in integrated-circuit technology, the exponential growth predicted by Moore's law has held true. But the handwriting is now clearly on the wall: Moore's law cannot hold forever. What lies beyond Moore's law?

In CSE599, we will examine alternative computing machines. We will start by considering present-day IC technology: How it drives computer design, and what are the physical limits. We will then examine some of the proposed alternatives to our sequential digital machines: Neurobiologically inspired computing, quantum computing, and DNA computing. Can these ideas be made to work?  What are the technology drivers?

Our goal will be to quickly develop the requisite background in these subjects, and then to develop intuition about the real limitations and promise of each technology.

Course Syllabus

      1.  Introduction:  Why do digital computers work the way they do?
                IC fabrication, Si and SiO2, transistors, wire, digital logic
                Limitations and benefits of machines that use discrete mathematics
                Information representations: Machine state, alternative ways to encode information
                Silicon-technology scaling: How, why, the physical limitations, the technological limitations
      2.  Theoretical Considerations in Computer Science
                The foundations: Automata, Turing machines, computability, halting, Goedel undecidability
                Hard problems: P versus NP, PSPACE
                Ill-posed problems: Algorithmic complexity
      3.  Information Theory
                Algorithmic definition of information
                Communicating information: Noise, channel capacity, signaling
                Error correction coding
                Extending error-correction principles to computation
      4. Thermodynamics
                The laws of thermodynamics and computing
                Noise, entropy, reversible computation
                Digital versus analog: Noise, accuracy, dynamic range, adaptation, density of states
      5. Neurobiology , neuronal computation, neural networks
                Neurons, dendrites, axons, synapses
                Signals and signaling in the nervous system
                Computation in nervous tissue: Local learning, continuous adaptation, LTP, LTD, development, growth
                Information coding in the nervous system
                Neural-network models: History, distributed representations, learning algorithms
                Spike-based computing
      6. DNA computing
                DNA, RNA, protein synthesis, base pairs, ligands
                Computational premise: Mapping sequential computations to DNA, self-assembly, Turing completeness
                Technology and applications: Errors and correction, beyond toy problems
      7. Quantum computing
                Spin, phase, states, superposition, Dirac notation
                How does wavefunction coherence enable computation?
                Quantum information theory
                Technology: NMR, cavity QED, SQUIDS
                Extracting the results from the machine
                Factoring (shor's algorithm), other applications
                Wavefunction decoherence, error correction

Comments to: cse599-webmaster@cs.washington.edu