Complexity and Recursion

Synopsis

Preamble Synopsis

How is it possible that only a small number of genes can code for the shape of a tree? How can bees maintain a complex social structure and create beautifully and efficiently organized hives with such small brains? Why is it so that we still cannot forecast the weather for any significant amount of time despite the truly incredible computing power of modern super computers? Indeed, how is it conceivable that trillions of neurons create intelligent behavior?

Answers to such questions have proved hard to come by. Surely, it is remarkable that modern science could predict the emission spectra of atoms with stunning precision or understand the basic laws that govern the universe decades before any of these questions had even a hint of an answer.

Ultimately, the reason as to why these questions are so hard is that they pertain to complex systems. On the one hand, complex systems are so ubiquitous that it is easy to overlook them, on the other hand, when not overlooked, they seem to be so bewildering as to defy explanation forever. Fortunately, over the last few decades, enormous progress has been made. Especially so on the qualitative side, although there are very significant quantitative results as well.

This course will investigate the mechanisms and notions that underlie the complex behavior so common in the natural world and discuss fundamental answers. It will be argued how interaction and recursion are two essential mechanisms, and how complex systems can lead to emergent phenomena that defy an atomic explanation.

In order to get a good grip on this extraordinary topic, we will explore the world of complex systems and their fundamental mechanisms through lectures, seminars and programming.  But why programming? Few would argue that a culture can readily be understood without learning its language. Similarly, a deep understanding of complex systems and emergent phenomena is virtually impossible to attain without a core knowledge one of its two complementary languages: Mathematics and Programming. Indeed, trying to avoid either is akin to an attempt to ‘understand’ driving by reading up on the rules of the road. Regrettably, the mathematics of complex systems can get very hard very quickly but the required programming skills needed are surprisingly accessible.

Now this is exciting since an understanding of how coding works is immensely useful in a huge number of fields while in the context of this course, it is the tool that enables one a hands-on experience and a means to explore systems in ways that is not otherwise possible. By actually engaging in coding oneself, it will become abundantly clear why the notions of computation play such a key role when trying to unravel the mysteries of complex phenomena. And … prior programming or coding experience is not required!

Toward the end of the course, we will discuss why, out of necessity, living systems may well need to be complex and how emergent behavior and computing go hand in hand. Indeed, I will argue that the emergence of life, given the existing laws of nature, is inevitable and that consequently life must be abundant in the universe! (But do feel free to disagree on this one, it’s the discussion that counts not the outcome).

After completing this course, you will have a deep understanding of complex systems, emergent phenomena and the workings of computational devices. It will be clear why the principles behind complex behavior need not be complicated, that we can understand why ant or bee colonies can perform their astonishing feats and that one of the great challenges of 21st century science is the discovery of universal laws of complexity.

Syllabus

Syllabus

PLEASE NOTE: Below is the tentative syllabus. The finalized syllabus will be made available on the first day of classes. The sequence of the topics may be modified but the topics themselves are unlikely to change significantly. There will be two types of lecture: The first type consists of one or more small presentations, lecture material and interactive sessions. The second type consists of lecture material, interactive sessions and hands-on lab-style work where complex systems are explored with the help of computer programs.

Week One

Topic: Could Life be a Complex System?
Readings: Complexity – A Guided Tour, chapters 1, 12; A New Kind of Science, chapter 1

  • Lecture 1: Course Introduction and Overview of Complex Systems
  • Lecture 2: The social amoebae Dictyostelium, Ants, Bees
  • Lecture 3: Multi-cellular life, replicate and modify
  • Lecture 4: Setting up a programming environment

Week Two

Topic: Foundation I - Recursion
Readings: Complexity – A Guided Tour, chapters 3, 4; A New Kind of Science, chapter 2

  • Lecture 5: Overview of recursion and recurrence
  • Lecture 6: Algorithms
  • Lecture 7: Interacting units
  • Lecture 8: Running Programs

Week Three

Topic: Foundation II – Exploring the World through Computation
Readings: TBA

  • Lecture 9: Modeling Complex Phenomena
  • Lecture 10: Elements of a Computer Language
  • Lecture 11: Writing and Executing a Program
  • Lecture 12: Midterm

Week Four

Topic: Towards Complex Systems
Readings: TBA

  • Lecture 13: Chaos
  • Lecture 14: Universalities in Dynamical Systems
  • Lecture 15: Fractals
  • Lecture 16: Exploring Chaos and Fractals Hands-on

Week Five

Topic: Exploring Complex Systems
Readings: TBA

  • Lecture 17: Cellular Automata
  • Lecture 18: Turing Machines and Hands-on Cellular Automata
  • Lecture 19: Universalities in Computation
  • Lecture 20: Networks

Week Six

Topic: Life can be Viewed as a Complex System
Readings: TBA

  • Lecture 21: The cell as a complex system and as a computer
  • Lecture 22: The origin and inevitability of life
  • Lecture 23: Group presentations and discussions
  • Lecture 24: Final

Requirements

Requirements

This course is highly interactive and hence being prepared and willingness to engage actively in discussions is essential.

For each class there will be some readings of modest length and everyone will be expected to have done them before class. For each reading, one or two students will be asked to give a short presentation mostly focused on ‘their take’ of the material. There will also be an opportunity for brief ‘you-choose’ presentations where anything related to the topic at hand can be discussed. Usually, the presenter(s) will be selected one or a few days before the reading is due. There also will be larger group projects to be presented at the end of the course. Suggestions for group projects will be available. However, groups will be allowed to propose topics from virtually any field of study. Each group will consist of about 3 students.

During the Lab Sessions, participants will learn how to write basic programs and how to use template programs that will be provided to explore complex systems. Some lab sessions will have a graded assignment that generally can be completed by the end of the session. These tasks will be limited in scope and mainly serve as a guide to absorb the materials. Students will be allowed to work in small teams of 2 to 3 persons.

The midterm and final are individual assessments.

A summarized breakdown of the assessment weightings can be found below (details will be discussed on the first day of class):

Assignments 20%
Quizzes/Midterm 20%
Presentations 30%
Final 30%

Bibliography

Bibliography

Main Reading

Complexity: A Guided Tour, Melanie Mitchell
Selected Journal Articles

Additional Reading

A New Kind of Science, Stephen Wolfram
(Note: This book can be read online at: http://www.wolframscience.com/nksonline/toc.html)

Further Reading and Resources

Chaos – Making a New Science, James Gleick
Investigations, Stuart Kauffman
Fractals for the Classroom, Peitgen, Jürgens, Saupe
Laws of the Game, Manfred Eigen and Ruthild Winkler
Origins of Life, Freeman Dyson

Scroll to Top