in Programming

This entry is part of the BlogBook called "Programming Wisdom".

In my continuing series on why software is special, motivating writing a book about it, this post discusses how software is *chaotic*.

Here I refer to the mathematical definition of *chaos*, which I will define as: "A chaotic system is one in which small changes in the initial conditions can cause large and unpredictable changes in the system's iterated state." This is based on the mathematical definition(s), but simplified for our purposes. It's not just a word, it's a quasi-formal concept.

Every clause of the definition is important. In particular, people often leave out the "unpredictable" part of the definition of chaos, but you do not have chaos if everything is predictable. If you are at the top of a very round, smooth hill with a heavy ball, the final destination of the ball is predictably determined by the initial direction you give it when you drop it. This is what physicists would call "unstable", but it is not chaotic.

Every computer science curriculum worth anything will talk about the fundamental limits of computing, such as the halting problem in all of its guises. One of the most important things to carry away from that seemingly-academic discussion, even if you have no interest in pursuing further academics, is that **unpredictability is fundamental to the building blocks of software**. Once you start using Turing Machines, you have entered the realm of chaos. A single bit changed in the data or the program can have arbitrarily large effects, and in the general case, you can not predict what those effects are, not even in theory.

Software is almost the canonical embodiment of mathematical chaos. You can control and limit the chaos to some degree, but there is a boundary beyond which you fundamentally may not pass, and the reality of this boundary is so thoroughly embedded in the way we program that it is almost invisible. (The people who can best help you see this boundary are those who are studying ways to prove correctness in programs. They push the frontier a little further back with great effort and cleverness, and for this I salute them, but they will never be able to completely remove the chaos.) Per my earlier discussion about the lack of spatial separation, the full state space of a system is inevitably incomprehensibly large, leading to a lot of "room" for chaos to manifest, more than we could ever hope to examine. ("Room" grows exponentially in the size of the computer's memory.) This makes the system more unpredictable in practice, even if in theory the full behavior of the program could be understood. And being discrete, even the smallest change of a single bit can have arbitrarily large changes in the evolution of a program's state space.

Many other engineering disciplines certainly encounter chaos, though most try to minimize it, because unpredictable systems are generally less preferable than predictable ones. Even those that embrace it try to contain and minimize it; studying chaos can help you build a better muffin batter mixer but you wouldn't build the entire bread factory's mechanisms to function mathematically chaotically. (If you did wish to invoke chaos for some reason, you'd do it with software managing the system. The machines would still be designed to function non-chaotically.)

It can be very valuable for a computer programmer to take some time to study some of the characteristics of chaotic systems; I don't think a truly mathematical approach is necessary, so an informal overview and some time with a fractal-generation program should suffice. Things like "attractors" have obvious correlations to how software functions. You'll get enough practical experience once you start coding on your own, once you know what you're looking for.