From Turing Machines to Black Holes and Neurons

Harvard GSAS Mini-Course, January 2022

**GSAS Event Page**: link.

**Meeting Time**: January 10-14 & January 17-21 10:00am-11:50am Eastern Time.

**Google Calendar**: link.

**Blog Post**: link.

**Instructor**: Chi-Ning Chou (he/him/his; they/them/theirs)

- Website: http://cnchou.github.io
- Email:

**Guest Speakers**:

- Lijie Chen (MIT) on
*“Efficiency of Algorithms and the Sorites Paradox”*. - Xun Gao (Harvard) on
*“Quantum Correlations: the Resources Making Quantum Machines More Powerful”*. - Khadijeh Sona Najafi (IBM & Harvard) on
*“Quantum Machine Learning from Algorithms to Reality”*. - Angel Hsing-Chi Hwang (Cornell) on
*“Into the Unknown: (De)constructing Creativity in the Age of Human-Machine Partnership”*. - Zhiqian Wang (MassArt) on
*“A Road to Totality: Between Art and Computation”*. - Brabeeba Wang (MIT) on
*“Animal Intelligence: Flexible Computation Under Uncertainty”*.

**Teaching Staff**: Avantika Agarwal, Kartikeya Arora, Salvador Buse, Aaron K. Clark, Erick Galinkin, Simone Maria Giancola, Aman Goel, Reijo Jaakkola, Pawan Mishra, K Prahlad Narasimhan, Tirukkovalluri Sri Sowmya, Mostafa Touny.

**Overview**: We are in the era of computation. Everything from a spacecraft to your digital toothbrush has a computer inside it. Meanwhile, physicists told us that physical systems such as black holes are doing some kind of computation and neuroscientists told us our intelligence is built on top of small computations by neurons. What do they really mean by computation therein? Does computation mean the same thing in different fields? Furthermore, do we really understand what computation is?

In this mini-course, we are going to revisit the concept of computation through three different perspectives starting from mathematics, to physics and biology. Through theories, examples, and experiments, we are going to see the similarities and differences between these disciplines. The aim of this mini-course is to remind people of the diverse nature of computation and envision the possibilities of future interdisciplinary research.

There will be three modules and each contains three 50-minute interactive lectures and 1-3 guest talk(s). The first module focuses on the mathematical foundation of computations in which the students will learn the concept of Turing machines, computability, reductions, and most importantly, the underlying philosophy. The second module is about the computations in the physical world where we will launch from classical mechanics, to statistical mechanics, quantum mechanics, and gravity. The third module looks into the computations in biology, ranging from genomes, evolution, to neuroscience.

**Prerequisites**: No math or science prerequisites are required but we expect the students to be comfortable with seeing simple equations. We are particularly welcoming students from any background. The only requirement is having the willingness to communicate with and being respectful to people from different backgrounds.

**Policies and expectations**: We expect students to attend as many lectures and activities as possible. We will send out a survey one week prior to the mini-course for students’ availability and potentially adjust the times accordingly. Another survey for students to commit on their attendance (don’t need to commit to all the activities!) will be sent out once the lecture & lab times have been finalized.

**Learning outcomes**: By the end of the course, we hope that the students will all be able to:

- Understand the high-level story of each topic and be able to explain to non-experts.
- Appreciate and respect the different ways of thinking from different fields and perspectives.
- Comfortably communicate with people from different backgrounds.
- Build up interests in some of the topics and perhaps be willing to study further in the future.

The main components of the course are as follows:

**Main class meetings**: These will be interactive lectures, with the exposition and discussion guided by student questions and comments.**Labs**: These will be simple experiments demonstrating the key concepts learned in the class. We also welcome creative and artistic elements brought by the students!*(The in-person labs got cancelled due to the latest COVID regulations)***Guest talks**: These will be invited talks given by Ph.D. students or postdocs from relevant fields. The aim is to let the students have exposure to frontier research and thinking in each field.**Coffee chats**: These will be informal casual chatting sessions with free coffee and snacks made by the instructor. Due to the latest COVID regulations, this might not happen.**The Panel discussion (new)**: Near the end of the mini-course, we will host a panel discussion for the students to interact with every guest speaker and the lecturer.**Advanced sections (new)**: Outside the main lectures, the teaching staff will offer several 1-hour advanced sections covering a wide range of topics related to the course materials.

The course is composed of one introductory lecture, one concluding lecture, and three modules: (I) The mathematical foundation of computation; (II) Computations in the physical world; (III) Computations in the biological world. Each module will contain three 50-minute lectures where two of them (indexed by a,b) focus on theory and examples while the other (indexed by c) talks about philosophy and methodology. Each module will also have a lab and a guest talk.

**Introductory Lecture**: Motivation; Overview; Goal; Logistics. [slides].

Module I: The mathematical foundation of computation

Is there any problem that a mathematician cannot solve? This is known as Hilbert’s 10th problem and was one of the most important mathematical problems in the beginning of the 20th century. Intriguingly, the answer turned out to be negative. In fact, most of the problems in the mathematical world are unsolvable! To put this into a bigger context, the resolution of Hilbert’s 10th problem was a corollary of Turing’s great achievement of establishing the mathematical foundation of computation.

In this module, students will learn Turing’s mathematical formalization of computation as well as the two other central notions in the modern study of computation: asymptotics and reductions. Other computational notions such as non-determinism, randomness, and communications will also be discussed. The goal is to provide intuitions for students to think about the mathematical formulation of computation and be able to compare with the materials covered in the next two modules.

**Lecture I.a (Departure: Reasoning about Computation via Mathematics)**: Computational problems; Hilbert’s problems; Turing machines; Uncomputability Theorem. [slides].**Lecture I.b (Modern Developments: Models, Resources, Reductions)**: Other computational models; Circuits; Communication; Other computational resources; Nondeterminism; Randomness; Reductions; Cook-Levin Theorem; KW Games. [slides].**Lecture I.c (Reflection: Turing Machine and Reality)**: Mathematical Church-Turing Thesis; Philosophy of computation; Philosophy of science. [slides].**Lab I**: Have fun with reductions.**Guest talk I**: Lijie Chen on*“Efficiency of Algorithms and the Sorites Paradox”*.[*abstract*]

**Advanced section I.a**: Reijo Jaakkola on*“Undecidability of the Halting Problem and Gödel’s Incompleteness Theorems”*. [slides]. [*abstract*]

**Advanced section I.b**: K Prahlad Narasimhan on*“The Four-Color Theorem”*. [slides]. [*abstract*]

Module II: Computations in the physical world

Well before the apple falling on to Newton’s head, physicists had been searching for the underlying laws that govern reality. These beautiful mathematical descriptions explain how the stars move in a certain pattern, how small particles interact with each other, and so on. But “why” are these physical laws governing the universe rather than others? “What” are these physical laws doing and is there any underlying “problem” they are solving?

In this module, we are going to explore these questions through the lens of computation. Students will learn the basics of classical mechanics, statistical physics, quantum mechanics, and theory of gravity and peek into the connection to computation via “energy minimization” and “entropy maximization”. The goal is to (i) learn how physicists think, (ii) compare the concept of computations in the physical world to the mathematical formulation discussed in module 1, and (iii) build up sufficient language and knowledge for the next module.

**Lecture II.a (After the Falling Apple: Classical and Statistical Mechanics)**: Lagrangian and Hamiltonian mechanics; Statistical physics [slides].**Lecture II.b (Two Extremes: Quantum and Gravitational Theories)**: Quantum mechanics; Gravity and black holes [slides].**Lecture II.c (The Road to Reality: New Insights from Computation?)**: Pancomputationalism; Computation in physical systems; Physical Church-Turing Thesis; MIP*=RE [slides].**Lab II**: Gravity circuits.**Guest talk II.a**: Xun Gao on*“Quantum Correlations: the Resources Making Quantum Machines More Powerful”*. [*abstract*]

**Guest talk II.b**: Khadijeh Sona Najafi on*“Quantum Machine Learning from Algorithms to Reality”*. [*abstract*]

**Advanced section II.a**: Erick Galinkin on*“Information Geometry”*. [slides].**Advanced section II.b**: Simone Giancola on*“Simulated Annealing”*. [slides]. [*abstract*]

**Advanced section II.c**: Tirukkovalluri Sri Sowmya on*“Basic of Quantum Computing & Future Directions”*. [*abstract*]

**Advanced section II.d**: Avantika Agarwal on*“Quantum Complexity Theory”*. [*abstract*]

**Advanced section II.e**: Kartikeya Arora on*“Quantum Computing from a Condensed Matter Perspective”*. [*abstract*]

**Advanced section II.f**: Chi-Ning Chou on*“When Black Holes Meet Computational Complexity”*. [*abstract*]

Module III: Computations in the biological world

Biology is the study of life. What is life? How does life form? What is the purpose of life, if there’s any? Unlike physics and mathematics, the challenges of reproducibility in biology, e.g., emergence properties and the precision in experiments, make it an extremely difficult subject to study. Statistical methods have been a prominent approach to establish biological knowledge while in recent years computational methods have arisen as a new angle to understand the biological world. Through the tango between biology and computation, how can the two inspire each other?

In this module, students will see various examples of the computational aspects of biology, including genomes, evolution, neuroscience, etc. The goal is to envision how the computational view can enrich understanding in biology and vice versa. In particular, we will be focusing on the open-ended nature of the living world and compare it with the previous two modules.

**Lecture III.a (Entering the Living World: Algorithms and Computations in Biology)**: What is Living Science; Computational Biology; Biological Computation [slides].**Lecture III.b (Two Mysteries: Evolution and Neuroscience)**: Evolution; Neuroscience [slides].**Lecture III.c (Challenges and Hopes: A Tango between Biology and Computation)**: Open-endedness; Emergence; The challenge and difficulty of studying biology; Mathematical ineffectiveness in biology [slides].**Lab III**: Computation and intelligence in slime mold.**Guest talk III.a**: Angel Hsing-Chi Hwang on*“Into the Unknown: (De)constructing Creativity in the Age of Human-Machine Partnership”*. [*abstract*]

**Guest talk III.b**: Zhiqian Wang on*“A Road to Totality: Between Art and Computation”*. [*abstract*]

**Guest talk III.c**: Brabeeba Wang on*“Animal Intelligence: Flexible Computation Under Uncertainty”*. [*abstract*]

**Advanced section III.a**: Salvador Buse on*“Computing with Chemistry: Turing Machines, Graph Colouring, and DNA”*. [*abstract*]

**Concluding Lecture**: Summary; Students’ Sharings; A Warning and a Wish. [slides].

The final schedule might be slightly different from the tentative schedule. The time zone is Eastern time and you can follow this google calendar.

The instructor will provide slides and additional notes available on the course website after each lecture. Optional readings and resources will also be posted on the course website. Before the course begins, we also encourage students to take a look at some of the references listed below.

Module I: The mathematical foundation of computation

**Articles**:

- Horswill, Ian. “What is computation?”, 2008, link.
- Wigderson, Avi. “The Godel Phenomenon in Mathematics: A Modern View.” Kurt Gödel and the Foundations of Mathematics (2011): 475, link.
- Davis, Philip J. “Toward a Philosophy of Computation.” For the Learning of Mathematics 3.1 (1982): 2-5, link.
- Knuth, Donald E. “Computer science and its relation to mathematics.” The American Mathematical Monthly 81.4 (1974): 323-343, link.

**Introductory Books**:

- Moore, Cristopher, and Stephan Mertens. The nature of computation. OUP Oxford, 2011, link.
- Barak, Boaz. Introduction to Theoretical Computer Science. Online, link.
- Rautenberg, Wolfgang. A concise introduction to mathematical logic. New York, NY: Springer, 2006, link.

**Advanced Books**:

- Wigderson, Avi. Mathematics and computation. Princeton University Press, 2019, link.
- Arora, Sanjeev, and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009, link.

**Fun reads**:

- Aaronson, Scott. “Why philosophers should care about computational complexity.” Computability: Turing, Gödel, Church, and Beyond 261 (2013): 327, link.

Module II: Computations in the physical world

**Articles**:

- Preskill, John. “Quantum computing 40 years later.” arXiv preprint arXiv:2106.10522 (2021), link.
- Gualtiero Piccinini and Corey Maley. “Computations in Physical Systems.” Stanford Encyclopedia of Philosophy, 2010, link.
- Yao, Andrew Chi-Chih. “Classical physics and the Church–Turing thesis.” Journal of the ACM (JACM) 50.1 (2003): 100-105, link.
- Piccinini, Gualtiero and Corey Maley, “Computation in Physical Systems”, The Stanford Encyclopedia of Philosophy (Summer 2021 Edition), Edward N. Zalta (ed.), link.

**Introductory Books**:

- Feynman, Richard P., Tony Hey, and Robin W. Allen. Feynman lectures on computation. CRC Press, 2018, link.
- Penrose, Roger. The road to reality: A complete guide to the laws of the universe. Random house, 2005, link.
- Mezard, Marc, and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009, link.

**Advanced Books**:

- Mézard, Marc, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications. Vol. 9. World Scientific Publishing Company, 1987, link.
- Sakurai, Jun John, and Eugene D. Commins. “Modern quantum mechanics, revised edition.” (1995): 93-95, link.
- Alber, Gernot, et al. Quantum information: An introduction to basic theoretical concepts and experiments. Vol. 173. Springer, 2003, link.

Module III: Computations in the biological world

**Articles**:

- Schnitzer, M. Biological computation: Amazing algorithms. Nature 416, 683 (2002), link.
- Chelly Dagdia, Z., Avdeyev, P. & Bayzid, M.S. Biological computation and computational biology: survey, challenges, and discussion. Artif Intell Rev 54, 4169–4235 (2021), link.
- Piccinini, Gualtiero. “Computationalism.” The Oxford handbook of philosophy of cognitive science. 2012, link.

**Books**:

- Nowak, Martin A. Evolutionary dynamics: exploring the equations of life. Harvard university press, 2006, link.
- Jones, Neil C., Pavel A. Pevzner, and Pavel Pevzner. An introduction to bioinformatics algorithms. MIT press, 2004, link.
- Gillespie, John H. Population genetics: a concise guide. JHU Press, 2004, link.

**Fun reads**:

- Stanley, Kenneth O., and Joel Lehman. Why greatness cannot be planned: The myth of the objective. Springer, 2015, link.
- Schrödinger, Erwin. What is life?: With mind and matter and autobiographical sketches. Cambridge university press, 1992, link.
- Mayr, Ernst. This is biology : the science of the living world. Harvard University Press, 2001, link.
- Banatre, Jean-Pierre, et al., eds. Unconventional Programming Paradigms: International Workshop UPP 2004, Le Mont Saint Michel, France, September 15-17, 2004, Revised Selected and Invited Papers. Vol. 3566. Springer Science & Business Media, 2005, link.

We would like to create a learning environment in our class that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, ability, etc.). We (like many people) are still in the process of learning about diverse perspectives and identities. If something was said in class (by anyone) that made you feel uncomfortable, please talk to us about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with us. As a participant in course discussions, you should also strive to be open-minded and respectful of your classmates. (Statement modified from one by Dr. Monica Linden at Brown University.)

If you have a physical or mental health condition that affects your learning or classroom experience, please let us know as soon as possible so that we can do our best to support your learning (at minimum, providing all of the accommodations listed in your AEO letter if you have one). (Statement adapted from one by Prof. Krzysztof Gajos.)

Everyone can benefit from support during challenging times. Not only are we happy to listen and make accommodations as needed, we can also refer you to additional support structures on campus, including, but not limited to, the below.

- Bureau of Study Counsel
- InTouch
- Counseling and Mental Health Services, 617-495-2042
- Let’s Talk
- Room 13, 617-495-4969

**Q**: If I don’t have a strong math and science background, what will I learn and will there be any difficulties?

**A**: Most of the lectures will focus on the high-level stories and the underlying philosophy so will be very accessible to anyone! The instructor will also make sure more knowledgeable students won’t dominate the discussion and create a friendly environment.

**Q**: What if I already know most of the materials, what will I get from this course?

**A**: If this is the case, we encourage you to talk to us in advance. In general, the course materials won’t touch the details of each subject and instead focus on high-level stories and comparison with each other. This should provide you with new angles and insights into the subjects you originally were familiar with. Advanced and extra reading/reference materials will be provided on request.

**Q**: Is there homework for the mini-course?

**A**: No, but we will provide food-for-thought questions and brainstorming problems at the end of each lecture.

**Q**: Will all the lectures be recorded?

**A**: Yes, the recording link will be sent out once available and in long term will be posted somewhere publicly.