Is Samsara Turing-Complete?

Prelude

Today we completed two years of study on Mipham Rinpoche's the Beacon of Certainty. Anyen Rinpoche concluded with final comments and notes, and for good dependent arising for future teachings on the Beacon of Certainty, went back to the beginning and read the introduction to us again in Tibetan. Afterwards, we had a magnificent tsok and mandala offering.

This caused me to reflect on some earlier shedra classes with Rinpoche, even before we started studying the Beacon of Certainty. When I logged onto blogger, I saw that I'd started writing a post a while back that I never finished. Today seems like a good day to do that :-)

The 12 Links

Two and a half years ago, on April 12th of 2008, Anyen Rinpoche held yet another excellent shedra class. In particular, Rinpoche took some time to go over the twelve links of dependent arising (often called "twelve links of interdependent origination") in some detail. As is usual for his classes, it was a vibrant experience: high energy, lots of exchange and discussion, and very interesting material. However, one thing in particular stood out: Rinpoche made it a point to show that the twelve links are recursive.

To those of us that have studied this before (or, in fact, have a passing familiarity with the twelve links), that may seem like a no-brainer. But it's actually quite interesting to explore. Before we do, though, let's take a quick look at what Wikipedia has to say about recursion (the added emphasis in italics below is mine):

"Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are almost parallel with each other the nested images that occur are a form of recursion."

I believe that Anyen Rinpoche was making an explicit point about the primary causal (as opposed to the secondary or assisted causal) dependent arising links generating new "instances" (lifetimes) of twelves links, with each of those generating other twelve links. Or, perhaps said in a better way: if it takes three lifetimes to complete a cycle of the twelve links, and if each of those lifetimes contains the results from a previous life as well as the seeds for a future life (e.g., previous links and future links), then the twelve links are recursive. They are recursive because a lifetime is not only the ripening of one part of the twelve links from a previous life, but also the generator of more interdependent links for future lives, ad infinitum.

Let's take a look at what else Wikipedia says:

"Newcomers to recursion are often bewildered by its apparent circularity, until they learn to appreciate that a termination condition is key."

A termination condition! Guess what our termination condition is? Purifying the obscurations, typically said to occur between link seven and eight. If the twelve links is a recursive construct, then the termination condition is cutting the cycle of rebirth.

Turing Machines

So what does all this have to do with Alan Turing and his theory about computers? Let's back up a bit... how did Rinpoche's mention of recursion cause thoughts of Turing-completeness? Well, the thought process went something like this:

1. The 12 links are recursive.
2. Recursion is the basis for several programming languages (e.g., Lisp); not only that, but all modern languages that user iteration can be reformulated to use recursion instead (see this link).
3. Most programming languages are Turing complete (see this link). To be Turing complete, it is enough to have conditional branching (an "if" and "goto" statement), and the ability to change arbitrary memory locations.
4. If recursion provides a tool for enabling Turing completeness in computer science, how much of a stretch would it be to think of Samsara as Turing complete?
5. What would that even mean?
   

There are several concepts that should be introduced here, before we start tackling analogies:

• a Turing machine
• Turing completeness
• a universal Turing machine

For the first bullet, this Wikipedia article provides a nice definition:

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer [...] Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They help computer scientists understand the limits of mechanical computation.

So, a Turing machine is often simply a thought experiment used to clarify complex ideas in computation. Then what's Turing complete, and how does that related to a Turing machine? Referencing Wikipedia again:

[...] In practice, Turing-completeness means that the rules followed in sequence on arbitrary data can produce the result of any calculation. A device with a Turing-complete instruction set, and an infinite memory and infinite lifespan, is the definition of a universal computer.

In other words, a Turing complete system is one that can simulate a Turing machine. So what about a universal Turing machine? On another page, we have this:

In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of machine to be simulated as well as the input thereof from its own tape.

In essence, the universal Turing machine generalizes for any input.

Does the Analogy Fit?

The 12 links of dependent origination cover the complete range of human experience. It is a perspective distinctly human: physical, mental, emotional. But when you look closely, it boils down to input and operation. Analysis and action. These could very easily be mapped to the "if" and "goto" necessary for Turing completeness. What's more, given the concepts of karma and the storehouse consciousness of alaya, we have memory. The repetition of karmic patterns is the "reading" of the memory. The mutation of patterns in the alaya is an effort to bring about desired effects, overriding old patterns.

This obviously deserves a more thorough analysis, but it seems that there's certainly enough here to justify further pursuit.

Digital Physics

On an equally weird note, when reading up on this topic for the blog post, I came across this gem:

In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable. Therefore, the universe can be conceived as either the output of a computer program or as a vast, digital computation device [...] Digital physics suggests that there exists, at least in principle, a program for a universal computer which computes the evolution of the universe. The computer could be, for example, a huge cellular automaton (Zuse 1967[9]), or a universal Turing machine, as suggested by Schmidhuber (1997), who pointed out that there exists a very short program that can compute all possible computable universes in an asymptotically optimal way.

So someone's already beat me to this idea (or a variation of it), and they did so in 1957. Many others contributed to this philosophical and physics ideas since then. In particular, one of the greatest modern general relativists, John Archibald Wheeler, had this to say (from the same Wikipedia article):

It is not unreasonable to imagine that information sits at the core of physics, just as it sits at the core of a computer. It from bit. Otherwise put, every 'it'—every particle, every field of force, even the space-time continuum itself—derives its function, its meaning, its very existence entirely—even if in some contexts indirectly—from the apparatus-elicited answers to yes-or-no questions, binary choices, bits. 'It from bit' symbolizes the idea that every item of the physical world has at bottom—a very deep bottom, in most instances—an immaterial source and explanation; that which we call reality arises in the last analysis from the posing of yes–no questions and the registering of equipment-evoked responses; in short, that all things physical are information-theoretic in origin and that this is a participatory universe.

This is beautifully stated. Sounds similar to things that Chogyam Trungpa has said.

Though I am not a fan of the anthropic principle, I do find potential variations on it interesting to ponder. As a result, I have added The Anthropic Cosmological Principle (forward by Wheeler) to my Amazon wishlist. Wheeler discusses this theme more in his article "Information, Physics, Quantum: The Search for Links" available in the book Complexity, Entropy, and the Physics of Information (Amazon, Google books).

Back to Samsara

All of this is a lot to digest. One thing that this encourages me to do, though, is spend a lot more time pondering the 12 links of interdependence. Jigme Lingpa provides an excellent introduction to these, along with exercises for the reader :-) I've spent a little time following his instructions, but not nearly enough.

Once I do, I expect to have further insight into the computability of conventional reality. I don't imagine such investigations to bring anything more than just another way of viewing the well-understood problem of the human condition in samsara. That being said, fresh perspectives are often useful.