Natural Computation and Self-Organization:

The Physics of Information Processing in Complex Systems

Instructor: Professor Jim Crutchfield (Physics and CSC)
Assistant: Chris Ellison (Physics and CSC).
WWW: cse.ucdavis.edu/~chaos/courses/ncaso/

Catalog number: Physics 250, Special Topics (CRN 36972)
Level: Graduate
Units: 3 (to become 4 units, on UCD approval of course)
Times: TuTh 0210-0330 PM
Location: 158 Roessler
Office hours and locations:
Crutchfield: W 0300-0400 PM, 1109 MSB
Ellison: M 0300-0400 PM, 1227 MSB
Poster: [jpg]

The course explores how nature's structure reflects how nature computes. It introduces intrinsic unpredictability (deterministic chaos) and the emergence of structure (self-organization) in natural complex systems. Using statistical mechanics, information theory, and computation theory, the course will develop a systematic framework for analyzing processes in terms of their causal architecture. This is determined by answering three questions: (i) How much historical information does a process store? (ii) How is that information stored? And (iii) how is the stored information used to produce future behavior? The answers to these questions tell one how a system intrinsically computes.

The course will develop tools to describe and quantify randomness and structure. It will show how they are necessarily complementary and how they are intimately related to concepts from the theory of computation. A number of example complex systems—taken from physics, chemistry, and biology—will be used to illustrate the phenomena and methods. The course will also take time to reflect on the intellectual history of these topics, which is quite rich and touches on many basic questions in fundamental physics and the sciences and technology generally. New topics this year include complex materials and computation in quantum systems. The course will bring students to the research frontier in nonlinear physics and complex systems.

Outline: (Course Syllabus [PDF] [HTML] )

• Weeks 1-3: Self-Organization (Nonlinear dynamics and pattern formation)
• Weeks 4-5: Information Processing (Introduction to information theory)
• Weeks 6-8: Natural Computation (Computational mechanics)
• Weeks 9-end: Projects and Supplemental Topics.

Complex systems to be analyzed:

• Low-dimensional chaos and routes to chaos
• 1D/2D spin systems
• Cellular automata
• Hidden Markov models
• Quantum dynamical systems
• One-dimensional materials

Audience: Graduate students in physics, mathematics, computer science, engineering, mathematical biology, and theoretical neuroscience. Others also welcome.

Reference materials:

1. Books:
   • Elements of Information Theory, T. M. Cover and J. A. Thomas, Second Edition, Wiley-Interscience, New York (2006).
   • Nonlinear Dynamics and Chaos: with applications to physics, biology, chemistry, and engineering, S. H. Strogatz, Second Edition, Addison-Wesley, Reading, Massachusetts (2001).
2. Computational Mechanics Reader.
3. Lecture notes.
4. Software tools.
5. Supplemental Readings for historical background, projects, programming, and amusement.

Course Work:

1. Assigned readings for each lecture.
2. Weekly Problem Sets.
3. Research Project:
   • Program or written report: Orally presented as final exam.
   • Project Presentation Schedule.
   • Report Organization.
   • Example projects can be found here.