The Necessity of Determinism

Perspective is relative. You might, for instance, see a desktop computer as an item you purchase, and then update with various software to complete the package. A stand-alone machine acting as a tool to help you manage your data. This has been our traditional view of computers, and until recently it has been mostly correct.

If you take an abstract view, any given computer has exactly F ways to fail. By failure, I don't mean small annoying bugs, but rather total and complete melt down of the platform to the point where it requires a significant fix: reboot, new hardware, or new software. It is unusable without intervention.

F varies, based on the hardware, operating system and any installed software. A couple of decades ago, with a simple IBM box, DOS 6 and a normal upscale vendor for peripherals, there might have been hundreds of ways for the machine to fail. Any of the core hardware could burn out, software could go wild, or the OS could find a reason to crash. The actual number doesn't matter, we far more interested in the way its changing, and why its changing.

In a sense, on using the machine to complete a task there was one way to success, and F ways to fail. The successful branch is overwhelmingly likely, but the size of F is not insignificant.


DETERMINISM AND ITS NON

There is a dictionary definition for the word determinism that describes it as a philosophical doctrine. A belief in cause and effect. In Computer Science however, we tend to use the term more as an objective property of a system, such as a deterministic finite automata (DFA). The transitions between states in the automata are driven deterministically by the input. There is an observable causal relationship. If the system does exactly what you would expect it to do, no more, and no less, then it is deterministic.

Computers, by their very nature are entirely deterministic. The CPU starts executing a fix series of instructions, such that given the same initial pre-conditions the results will always be the same. That deterministic quality, as we'll get into more detail, is very important for making the computers a useful tool.

Interestingly enough, although their behavior is predicable, computers can be used to simulate non-deterministic behavior. In at least a limited sense, the regular expression operator * eats up an arbitrary number of characters in a string until it is finished or the expression is proven to not match. a*b behaves differently depending on the input string, matching a string like annnnb, but not one like baaaaaa.

A common way of implementing this type of functionality in software is by using a non-deterministic finite automata (NDFA), which is a rather long way of describing an abstract machine with a set of internal states where the transition from one state to another is caused by a non-deterministic reaction to the input. You just don't know when the machine will change state.

You'd think that writing something on a deterministic computer to have non-deterministic behavior would be a complex problem, but they solved that rather early in our history by spawning off heaps of DFAs for each possible state that could exist. These possible transition automata may or may not exist, one input of which may collapse all of them into a single defined state. The NDFA may be any number of possible DFAs, but similar to Quantum probabilities, they all collaps down to one (or none) at the very end.

With this knowledge, it became easy to simulate a NDFA using a dynamic list of DFAs. Non-determinism, it seems, can be easily simulated. Or at least aspects of it.

A neat trick, but it also holds a broader understanding: non-deterministic behavior is easily emulated by determinism machines. Just because the essence of something is predictable, doesn't mean that everything you do with it will be predicable as well.


INCREASING WOES

Over the years, as the software has gotten more complex, the number of possible failures, F, has risen significantly. I believe it is rising exponentially, but proving that is beyond my horizon.

These days, there are many more reasons why modern desktop computers fail. Hardware, while getting cheaper is also less in quality. Software, while more abundant has outpaced it environment for complexity. Software practices have decayed over the years. Although modern operating systems are far more protective of themselves, there are still a lot of ways left to render a machine useless. New holes open up, faster than old ones are patched. And now of course, there are people actively trying to subvert the system for profit.

If it was just an issue of an exponentially increasing F exceeding our operational thresholds for stability, technological advancements would gradually reduce the issue. We'll eventually find stronger abstractions that help with reducing these problems.

However, indirectly, we've created an even worse problem for ourselves. One that is growing more rapidly than just the normal equipment or algorithmic failures.

As a stand-alone machine, we define the number of problems in a computer as F. If we link two machines by a network, this really doesn't change. The addition of networking hardware and software increases F, but linearly, relative to the new pieces. Failures on one machine, in very limited cases may cascade to another, but that is rare and unlikely. Each machines reacts to its data independently.

If one machine becomes responsible for pushing code and data to another machine, then everything changes. The two machines are now intertwined to some degree. F might not double, but there are all sorts of reasons why the second machine may easily clobber the first. As we see all of the different chips and micro-controllers of any standard PC as a single machine, we must now see all of them for both machines as one machine. Bind them correctly, and they are no longer independent entities. The two become one.

Once the interaction goes beyond a simple question answer protocol, where the exchanged data itself can contains failures, both devices are tied to each other.

With two machines and a rather large increase in F, the behavior of the whole new machine becomes rather less deterministic. Like the NDFAs, you can see the whole as the different permutations of its kids. A big machine containing two independent simulations of other machines. We can still follow the behavior of the boxes, but it is no longer as predictable. Small differences in execution order on either of the boxes may change the results dramatically. Subtle differences that mean non-determinism.


THE NETWORK IS A COMPUTER

Almost all of our modern machines are now interconnected to each other in some way. Internal corporate intranets connect to the Internet, which connect to our home networks. We have constant, easy access to our resources from a huge number of locations.

These increases in networking have revolutionized our machines, giving us unprecedented access to a near infinite amount of data (at least relative to one's lifetime). They helped integrate these tools into every aspect of our daily existence.

Software companies have utilized this connectedness to make it easier than ever to keep our current software up-to-date. There is a mass of interaction, at both the operating system level and the application levels. There are tools great and small for automatically patching, updating, reinstalling and coordinating the software on our machines. Windows XP, Java, Firefox, Acrobat Reader and dozen of other packages check on a frequent basis for the latest and greatest updates.

Even more interesting, if you account for all the virus, spam and phishing, then there is a massive number of sources out there interacting with your machine, trying (if not always successful) to give it new data, but also new code.

In essence, we've tied together our machines on so many different levels that we have effectively taken the millions and millions of previously independent computers and created one big massive giant one. One big massive giant, vulnerable one. With an F that is shooting well out of control.


BAD HAIR DAY

In its simplest form, all it takes to trigger a failure is for one of these updating mechanisms to install a change that renders the machine useless. Although there are checks and balances to prevent such things, history is full of great examples of nasty bugs getting lose in the last final round. It is inevitable.

So now we're becoming increasingly dependent on some poor coder in Redmond not having a bad hair day and accidentally scorching our boxes in a serious flame-out.

We're also dependent on some poor coder in the outskirts of civilization hopefully not having a good hair day and finding some new great way to subvert our machines for evil purposes.

If we started by thinking that F was in the hundreds, once you start counting all of the little possibilities, and how they might intertwine with each other, F grows at a frightening rate. There is a staggering number of reasons why an average desktop computer can now fail. Millions?

Given my experiences both at work and at home, these are not just infinitesimally small probabilities either. Over the last few years I've seen more hardware and software failures for an ever changing set of reasons, then I've seen in my whole career. Yet my usage and purpose and intent with my machines hasn't changed all that significantly. In truth I do use more web applications, and spend more time on my home machine then I used to, but the increases in failures has been way over my increases in usage.

My machine at work fails every time there is an system update to a piece of software I de-installed years ago. The box locks up, hangs, and turns off my database. This occurs multiple times per year. Several of the other auto-updates have crippled my box on occasion as well.

My friend's machine rebooted on a usb key insertion. My wifes machine has seized up for a number of unknown reasons.

If it were just me, I could forget about it, but virtually everybody I know has been entangled with at least one good computer bug story in the last couple of years. I'd start listing them out, but I don't think it necessary to prove the point, if you use your machine significantly, you're probably already aware of this.

In truth, it has been this way for a while.

Way back, I remember a system administrator telling me that Windows NT works fine, so long as you don't touch it. Sadly, he was serious, and defending the platform, which I had been verbally abusing because it keep crashing while running some test software. Nothing about the software should have effected the box, yet it was. Desktop computers have long since had a history of being flakier than any of their earlier cousins.


PHYSICAL DETERMINISM

A world-spanning massive super machine is both an interesting, but also a scary idea. Our little desktop machine is just a tiny piece of this bigger cube, entirely subject to its will, not ours. We only get to use it to complete our tasks if we are lucky. The F for this machine is way too high.

Purchasing a time-share on a massive computer is an interesting prospect, but would the circumstances be helped by achieving a massive bump in quality? If there was better security and better testing, would this change things?

These are very tough questions to answer simply. The short answer, often demanded by a younger, and less patient generation is that tools need to be deterministic, and that our current methods of interconnecting our machines defeats this entirely. In its own philosophy, we could say that the bugs are just the effects, the underlying cause is the lack of determinism.

To really understand that, we must start with a very simple observation. A bulldozer is a tool used by construction workers to move large volumes of earth from one place to another, and to flatten big areas. Bulldozers act as a tool to leverage the power of the machine to accommodate the drivers actions. The machine extends the driver's abilities.

It is entirely possible to build some type of Rube Goldberg contraption that given a setting, puts the bulldozer through a precise set of instructions. Physical, like the machines that help manufacturing lines assemble complex objects, completely non-computerized, just physics. We could build it so that the bulldozer is dropped off in a location, turned on and then it would do a specific operation like clear an area of land, or move a big pile of dirt somewhere. Set the switch to 40x40 and you get a huge square of land precisely flattened.

This type of mechanical automation could be used to remove the necessity of the driver, whom after all is just sitting there operating the machinery. The problem is that, in operating by itself, even with a very fixed simple set of rules, there are always unexpected circumstances that will creep up. In order to prevent serious accidents, someone must monitor the progress of the machine, and it is far better for them to be working with it while this happens, then for them to be sitting on the sidelines in a chair.

You can automate a factory because it is a limited controlled environment, but you'd never be able to automate something for an un-controlled one, common sense and safety keep us from doing so. Even the tiniest of accidents would draw a huge storm of protest.

The tool is best if it deterministically caries out the instructions of the driver, extending their abilities to do manual jobs. For both the factory and the bulldozer, determinism is a crucial aspect.


INTELLECTUAL PURSUITS

While that makes sense in the physical realm, people often differentiate between physical effort and mental effort. It is one of those class hold-overs where physical is seen as less desirable. In reality, most physical jobs demand a huge degree of mental energy, and sometimes this shifts over time. Los Alamos relied on human calculators in the pre-computer days, to do all of the "manual" calculation work, now easily seen as intellectual effort handled easily by a simple calculator. An Olympic class athlete's brain is working overtime trying to control their reactions to a massively precise level, a huge feat in thinking.

Effort of all kinds is really just a mix of some percentage between physical and mental. The two are closer than most people care to admit, some analogies relate the brain to being a muscle for thinking. Just another way to expend effort.

As anybody who has ever tried to automate a complex intellectual task knows, if you can't contain it there are as many possible obstacles to getting it to work correct as their are for the bulldozer. We cannot predict all of the variability of the real world, be it a mountain of dirt in a field, or a mountain of information in a corporation. It might, in some way be possible to account for all things, but realistically we need to assume that the possible failure conditions are infinite. Some are tiny, but it's still infinite.


REACTIVE INTELLIGENCE

In a world of unpredictability, we'd need a extremely complex calculation engine to be able to cope with an infinite variety of errors. Artificial intelligence is the much heralded savior for our woes. The only problem is that some people strongly believe that it is not possible, and have constructed proofs for such a truth. Many people believe that the failure in research to achieve it already is proof enough.

It is an interesting debate, and I'll digress a little into it. I have a tendency to think it is possible, but I think that most people studying it have grossly underestimated its inherent complexity. In a sense, they are looking for a simplified, pure, abstraction that provides this heighten capabilities. An abstraction that fits the neat ordering of our thinking.

I tend to see thinking as being intrinsically messy, and in many cases such as creativity, quite possibly flawed. I've often suggested that creative sparks are failures to keep things properly separated in our minds. A flaw, but a useful one.

A good simple example is the Turing test, a simple way of determining if something is "intelligent" or not. A person blindly interacts with a couple of entities with the intent of finding out which of them is a machine, and which is a human. If the person cannot distinguish between the two, then the computer's behavior has been deemed intelligent.

The problem with this test comes from the original episodes of Star Trek. Given a Vulcan -- an idealized, overly logical race of beings -- as the machine entity in a test against a human, most people would assume the Vulcan to be a computer. The logic and lack of emotion would be the keys. A Turning test for a human and a Vulcan would fail, showing the Vulcan as not being intelligent.

However, our idealized alien, at least in a TV-show script sort of way, is in fact an intelligent being quite capable of building star ships and traveling through the universe, a massively complex and clearly intelligent feat. Although it is only a TV show, it does act as a well constructed thought-based test. There is at least one alien intelligence we can conceive of that would intrinsically fail the Turing test. It would appear as a computer without intelligence, when it clearly wasn't.

I see this as hugely important in that the researchers are out there looking for something idealized. Something pretty, something with structure. They are searching in a specific location in a rather large field, my hunch is that their prey is hiding at rather an opposite location. And, as always, we can't search there, until our current path(s) take us closer to that area. I'd guess that we have to understand the structure of knowledge first, before we can learn to reliably extract out specific relationships.

It's likely to turn out that our own hubris-based definition of intelligence may actually be a big part of the problem.


GOING TO THE DOGS

What we consider as intelligence isn't often so. There are lots of examples, but fear and politics always provides the most interesting ones.

Over time, various media have discovered that shocking scary stories help sell the news. Because people like simple stories, there has been a tendency to report dog attacks, but only if the animal is described fully or partially as a Pit Bull. The term has come to invoke fear, and the common stereotype is of a vicious animal most often owned by drug dealers or other nefarious folk.

It's always a good simple story that gets a reaction. Often the dogs in question aren't even remotely Pit Bulls. The largest size of the breed is around 65-85 pounds, but its not uncommon to see stories about 120 pound "Pit Bulls".

It also doesn't matter that all other dogs bite, there are millions of Pit Bulls, nor that most of the supposed Pit Bulls are actually just mixes of many other breeds. Somehow this one domesticated animal has been granted superior dog capabilities. We've been living closely with the "child's nanny" for over a hundred years, they are the mascot of WWI, the RCA icon, appeared with children in films and have thousands of other cultural references. However, people wanted a villain, and the Pit Bulls were appointed.

Fatalities is where the anti-dog fanatics really like to focus, but they are slow to compare the dog-based numbers to those of other animals such as horses or even cows. Cars and guns kill millions every year, and somehow a tiny number of deaths becomes a growing epidemic. Yes, interaction with animals sometimes ends badly, that has always been true, no matter what animal is under consideration, domestic or wild. Anybody who has ever owned pets of any kind easily understands this.

Hype, misinformation, etc. aren't new, but we live in an age were it is becoming harder and harder to get away with this, and were ironically we are getting more and more of it. So, as a side effect of selling newspapers and nightly news casts, one of North America's most distinctive dog breeds has been used as the scape-goat for all of our angst about nature. Ironic, particularly in a period of intense "green" frenzy. And what more would we expect from this?

Of course some regional government, desperate to look "proactive" seizes the day and passes a breed-specific law banning Pit Bulls from an entire province. Sad, given that the negative hype was initially profit driven. The underlying facts aren't there, or are irrelevant. "Surely anybody who reads the newspaper would know that Pit Bull bites have reached an epidemic status and something needs to be done!"

The twist in all of this, is that we use our intelligence to build up and maintain our collective set of social rules. Because we live in an "intelligent" society we make rules and laws based on our understanding of the world around us. Smart people supposedly come together to lead us.

Ironically, the law didn't even really pass correctly. The dogs they were trying to address were mixes of Pit Bulls, but the law on docket is now restricted to only pure Pit Bulls, dogs with papers. It's all but useless, other than having taken away the newspapers ability to print good "Pit Bull" stories, and keep breeders from selling pups. It's a sad example of irrational fear gone completely wrong.

A new set of laws exist that don't do what they were supposed to, and the only reason they were created was to keep the public believing that a political party was actively trying to solve a problem (even if it was a trivial, non-existent one). It's insane, and clearly not intelligent. Even if you buy into the anti- "Pit Bull" hype, the resulting law itself is completely in-effective, a failure on top of a failure. The pure Pit Bulls have been all been replaced by mixed breeds. Nothings changed. All we have is another useless set of laws drafted by supposedly intelligent beings.


EXCEEDING DILBERTIZATION

This is but one simple example of how we have been building up our rules, our political systems, our organizations and our knowledge over the decades. We're exponentially piling on Dilbert inspired thinking to poorly solved unrelated problems. We have absolutely no way of disproving bad ideas or compressing our increasing mass of mediocre ones. Any new legislation from any existing body is equally as likely to be bad as it is good. And oddly, it is not just subjective taste, there are massive examples of clearly stupid short- or long-term ideas getting passed as though they were somehow intelligent. We live in a depressing era. Good for cartoonist, bad for intelligence.

Given the arbitrary mess of our collective knowledge, its easy to see how we appear as kids just barely beginning to qualitatively think about our surroundings. There was a time without zeros and negative numbers, pretty hard to conceive of now, but it wasn't that long ago. There will come a time when we can show an irrational bit of thought for what it really is. That, I guess, is probably were real intelligence lies, we're only partly there right now.

So what we know take for intelligence is barely such. We react to the world around us, but often at such a guttural level that it should never be confused with intelligent behavior. We still rely heavily on our older emotional capabilities, our intuition and of course superstition as aides in making many of our daily choices. Hardly rational, and barely intelligent.

Computer Science sits on the cusp of this. It is the one discipline that confronts this messy disarray of our knowledge and behavior on a daily basis. We guess what data we want, guess its shape, and then hope it works. The rampant changes in specifications come from the poorness of our guesses. If we were right initially, it wouldn't keep changing.

And our most venerable solution is by going around the problem with artificial intelligence. If we only had that, some people think, then our problems would be solved.

The biggest problem with our actually finding artificial intelligence is that like the Vulcan, Spock from Star Trek, it will simply annoy us, because it's rationale for doing things will be well beyond our own understanding. It will act in an intelligent manner, always.

It is very likely that we are in fact only half-intelligent. Simply a good step down a very long road to hopefully becoming a fully intelligent creature some day. Any good read of a daily newspaper will easily fuel that suspicion.

So, in all likelihood, even if artificial intelligence is discovered, it is likely something we don't want in our lives at this stage in our evolution. Some day perhaps, but not now. It just isn't going to help, and if Hollywood is to be believed, it will make things a lot worse.

If we can't have it, then our only option is to make all of our tools simple and deterministic. The tools have to work, no matter what environment that are placed in. We can't just keep adding rampant complexity and hoping that some magical solution will come along and fix all of the issues.


THE LITTLEST OF DETERMINISM

While I've gone on about the effects of failures, even at the smallest level our tools need to be deterministic as well. Certainly there was enough initial theory for GUIs about making everything on the screen be a direct result of the users actions. What happened to great ideas like avoiding modal behavior?

Good practice that we have been losing over time. Windows move on their own, focus shifts arbitrarily and dialogs pop up unexpectedly. It's an annoying type of sloppiness that degenerates the usefulness of tool.

We shouldn't have to stare at the machine to be able to ascertain its state, our actions alone should accomplish that. In such, a blind person should be in control of a simple program without ever having to look at the screen. The results on the screen should be absolutely deterministically caused by the user's actions. Strange erratic actions are non-deterministic.

Some early operating systems like Oberon did this exceedingly well, but as is often the case in software, with each new generating ignoring the knowledge of the past, much is lost while little is gained.

In general the idea of building non-deterministic tools is easily proven crazy. We clearly wouldn't be happy if the controls on a bulldozer or car, "sort of" worked. Forward mostly went forward, stop kinda stopped, etc.

And how useful would a calculator be if it randomly added or subtracted a few numbers from the result. If the results of 34 + 23 could vary by a couple of positions?

Tools are there to extend what we are doing, and they work when that extension is simple enough and predictable enough for us to have confidence in the results. When it has all become convoluted beyond a simple degree, we may have a tool, but using it is uncomfortable. A stupid semi-automated bulldozer is not an intelligent idea, it is an accident waiting to happen.


AND BACK AROUND AGAIN

Errors, networks, machines, intelligence, features, etc. all are tied together by the necessity of having that deterministic property for a useful tool. We must be able to predict the tools behavior.

We want our intellectual tools to work in the same way as our physical ones do. They should leverage our abilities in a simple and deterministic way, so that we can accomplish so much more. Tools should leverage our efforts.

Our modern computers are increasingly failing on this front. The number of failures is increasing rapidly, as we add new "features" we keep kicking it up to the next higher levels. At some point, the instability exceeds our abilities to construct it and the usefulness of the machine plummets significantly with each new increase in failures.

Our interfaces too have been increasingly failing. We have forgotten those simple attributes that should anchor our designs, things like determinism. We might have big fancy displays, spewing lots of colorful graphics, but if we can't trust what we are seeing, the enhanced presentation is all meaningless.

Artificial intelligence may some day grace us with its presence, but if anything it will complicate matters. We'll still need tools and they'll still need to be deterministic. It's usage will (and should) be limited and tightly controlled, possibly it is a similar dilemma to athletes taking steriods, something that clearly has an effect, but for obvious reasons is entirely non-desirable.

Determinism is a hugely important property of computers, that we've been letting slip away from us in our haste to make prettier systems. Where we think that tight bindings of the systems are making them easier to use, the truth is exactly the opposite. The more instabilities in the machine the more we stop trusting it. It is said that a poor workman blames his tools, but I'd guess that a foolish one uses undependable tools and should probably be blaming them.

Given that we have the foundations in Computer Science to understand why we should be building deterministic systems, our increasing failure to do so is all the more disconcerting. We want simple, but not at the cost of stability, a point where we have already sacrificed way too much.