The Real Zack Morris

Formal Nondeterminism

This is part three of my rant on the dismal state of computing and what to do about it. My last post was pretty vague and people have complained that I’m not offering tangible solutions. They also seem to fall into two camps, people who believe that we need to think clearly and mathematically if we wish to solve the problems in computing introduced by the human mind, and those who think that humans make a mess of computing and we need more intelligent software to do our programming for us.

After twenty years of this, I fall very strongly into the second camp. I have yet to meet anyone who has really mastered computers. And even the people who know computers inside and out tend to use ever higher level tools to do their work. A natural progression might be from assembly language, to C, to LISP, to Scala, to an exploratory tool like Matlab or Mathematica. If we take this to its logical conclusion, the highest level tool is strong artificial intelligence.

And it’s important to remember that these arguments are two sides of the same coin. In order to reach automatic computing, we need a formal foundation. As far as I can tell, none is coming from the private sector. It dictates that we can either use proper programming or make money, but not both. That leaves universities and other research institutions to do the heavy lifting. Unfortunately, they live in an ivory tower that doesn’t address real world needs like conveyability and incomplete specifications.

If we ever want to make any progress, I’m beginning to realize that we need a third path. One that takes into account human failings and incorporates them into the solution. Right now we have computer scientists on one hand and corporate masters on the other, both saying that we have to do things their way. Well, there are so many other ways of doing things that I just don’t know how much more time I can waste waiting around for them to see it.

If computers had begun more as physical manifestations (like Babbage’s Difference Engine), we might be using very different technology today. What do I mean by that? Well, in the real world, most tasks are trivially easy. Everything we do, from chopping vegetables, to pushing boxes around, to mowing the lawn, require almost no computing power. Sure they use some algorithms that we don’t typically think of computers as being good at. But they are a heck of a lot easier than something like Wolfram Alpha. Humans are remarkably adept at stepping through a series of tasks, like BASIC on a Commodore 64. We don’t think of computers as being useful for that. But that remarkable ineptitude of technology is exactly what I’m complaining about. I see it all around us, in everything we do. It’s been staring us right in the face for decades and most people aren’t even aware of it.

Growing up, we had a family friend in the carpentry business who didn’t think much of computers. He couldn’t get past the concept of a cursor. To him, a cursor is someone who swears a lot, and that’s exactly what he did whenever someone spoke well of computers. That always really bothered me, because he’s such an effective human being and deep thinker, that it seemed impossible that he couldn’t bend his mind around such a simple notion. But see, that WAS the problem. He was already skilled at his craft. Why should he have to bend his will to something that has no will?

Computers as they exist today can’t solve his needs or the needs of much of the population. If computing’s foundation was in tools instead of mathematical constructs, I have a hunch that many of the show stopping problems today like concurrency would have worked themselves out, and not just because more eyes would have been staring at them. It’s because we would have been working to solve real problems. Problems that the human mind is faced with. And those are intimately tied to everything that computers stink at today. This makes me question the foundation of computing and what we are trying to accomplish.

If I had the resources, I would start at the end and work backwards. We need more computers that have access to the real world through interfaces like X10 (only not as crappy). We need off-the-shelf macro languages where you demonstrate to the computer what you are doing, and it learns the logic required to accomplish the same thing. For example, moving a drill press through a range of motion and then training the computer to do it (and eventually do it better). Or giving a spreadsheet a list of numbers and the answer and letting it come up with the desired formula. Surprisingly, solutions similar to these already exist to some degree in primitive form. I’ve always wondered why they’re not mainstream, but I have a hunch that it’s because people want to be in the driver’s seat. We’re used to thinking of computers as dumb appliances and we aren’t quite ready to hand off responsibility to them. But that saddles us with needless drudgery.

This is all rooted in control issues. By that I mean a power struggle, like between a strict parent and a rebellious teenager. Right now computers are formally described down to their lowest level. At least we pretend they are. If you use a language like C or java or an operating system like UNIX, it’s actually impossible to prove that systems will do exactly what we want in every situation, as I showed in my last two posts. We like feeling like we understand what computers are doing, and we go to great lengths to pretend that problems don’t exist. But it’s all a fantasy. I first grasped the enormity of the problem about 15 years ago in college, but now more and more people seem to be waking up.

So if we accept the fact that we aren’t in control, to what degree are we willing to give up control? For some people, a bandaid like bounds checking of arrays in high level languages, or statically typed variables is enough that they can sleep at night. For others, they aren’t happy unless code has gone through rigorous static analysis and unit tests. Still others might use probability as a cushion, like six sigma reliability in air traffic control systems.

The remarkable thing to understand is that in the end none of this really works all of the time. It all comes down to the skill of the programmer. A bad programmer will write bad code in any language. And worse, detection of malicious code is still in its infancy so we’ll likely never even know. I was just discussing the problem with my girlfriend the other night. She wants to go into forensic accounting to sniff out fraud, but there is no real analog in the computing world. The best we can do is hope that an employee is a good person. Check out the obfuscated C contest. It’s difficult to detect maliciousness in a page of code, much less thousands.

If you still don’t believe me about the significance of this, I understand. But if you bear with me for a moment, I want to extrapolate. If control is just some statistic that satisfies us at some level (99% assuredness, whatever), then it must become smaller as complexity increases. There is only so much that a single human mind can grasp at once. But computer programs grow forever, often past millions of lines of code today. More and more of what computers do will inevitably become a mystery to us, no matter how much skill we have. Unpredictability is coming whether we like it or not.

So holding onto this fantasy of control makes us feel better, but at what cost? Are we willing to disenfranchise 90% of the world’s population because we believe they should internalize the same value system we have and bend their minds around the shortcomings of today’s technology? Don’t worry too much about this, because it will never happen.

If we instead picture a future where technology has been adopted by the majority of the population, what will it look like? Computers will inevitably change somehow. It’s like we are living in the sysadmin world of the 1970s before Xerox/Apple and GUIs brought computing to the masses. Nobody then could predict that computers would be used to share cat videos on facebook. Computers are evolving now in strange and unusual ways. All of the interesting frontiers in computer science are of a distributed nature and built on the democratization of technology.

And we can’t see past those boundaries because our thinking is rooted in systems of control that are becoming ever less relevant as time goes on. All I’m saying is that instead of putting so much time, energy and money into incremental improvements, perhaps we could consider another way. One that allows for a certain level of uncertainty in exchange for orders of magnitude more freedom.

The problem as I see it is that right now tremendous research is going into making processors faster, but this is futile. By its very nature, serial computation will do little to help people in the real world where distributed solutions like machine learning are so badly needed. We are thinking in terms of gigaflops, not teraflops or petaflops and beyond. Computer scientists just don’t seem to realize how cheap transistors have gotten and how easy it is to build a chip with thousands of cores. It’s far simpler to build an FPGA than the successor to the Intel i7. So they don’t even bother to notice when trivial solutions like MapReduce solve a difficult problem like search in effectively O(1) time. I just wonder how many other “difficult” problems in artificial intelligence have simple answers when we aren’t bound by the number of processing units.

I think this myopia comes from not having a general way to split a problem up into manageable pieces, some of which can be solved in parallel, and then put them back together again. Everything stems from this, because without parallelization, we have no good divide and conquer strategies. We can’t explore the large problem spaces surrounding issues like automatic algorithm generation and verification. Which means we’ll have to write algorithms ourselves, and that means no artificial intelligence, and worse: no relief for programmers forced to deal with ever-increasing levels of complexity. Until this changes, digital assistants will never be available to the masses.

Which is why it occurred to me that out of all of the problems that I’ve encountered in programming today, parallelization bothers me the most. Because it’s so elegant. It’s like finding a hole in your life raft. Sure you can put your finger over it, but it will eventually cause you a great level of discomfort. Anyone who thinks that we can work around it by avoiding iterators or other low level patterns is in denial about the chaos that happens in large systems.

Concurrency issues and other problems in these systems just never seem to go away, no matter how hard you try to move past them. We have some models that work currently, like ACID compliant databases. But you can still build a system on top of them that deadlocks. There is definitely no silver bullet here, perhaps even more so than at the language level. That’s because large concurrent systems are nondeterministic. Humans are simply unable to design them to be completely safe and predictable. And what’s a larger concurrent system than an artificial intelligence?

With so much riding on this, and after 50 years of research into parallelizing functions, has there been progress? Is there any hope? These questions need to be articulated and known solutions need to be summarized. Because right now it takes so many years of study to reach the point where we can even grasp these notions, that we can no longer see the forest for the trees.

What we really need is formal nondeterminism. We are living in a Newtonian age of classical computing but we’re moving into a kind of quantum era of probabilistic problem solving.

To get a glimpse of what I’m talking about, check out this article on ATNs, it’s very approachable and shows how a first-effort natural language parser works. Now imagine if the tree is enormous with millions of connections, and every path down each split in the tree needs to be executed in parallel if you have any hope of doing it in a reasonable amount of time. If you tell the parser to come up with its best guess in a limited timespan, then it just became nondeterministic because one branch might finish before another on subsequent runs. So there is a chance of getting a different answer each time, even from the same sentence. This is a remarkable result, and happens to humans all of the time when we are under pressure to solve a problem quickly.

So with AI, these probabilities are constantly coming up. With something like Apple’s Siri, it will be immediately obvious to every user that the computer doesn’t always interpret things correctly. But neither do we, if the room is noisy or we are distracted thinking about other things. And that’s ok. And as computing power increases, the computer has more time to work on a problem and so becomes more deterministic, at least for known sentences and contexts.

But the world is more random than that. Every situation is different. So a real AI will never really have complete certainty about much of anything, just like us. Everything will be shades of gray, which means computers will be fallible even when they are functioning properly, which hasn’t been much of a problem till now.

My solution to this is to not address that problem directly, because frankly there are a lot of really smart people out there, and if they haven’t solved it by now, they probably aren’t going to. I have a hunch why that is, but can’t prove it.

The gist of it is that we can write the equations for a quantum computer to crack encryption problems, but we need an actual quantum computer to solve them in real life. There is no way to simulate a quantum computer, because the computer emulating it would be much too slow. We’d get the answer 100 lifetimes of the universe from now or whenever. My sense of this is that even if aliens gave us the theory for intelligence today, we couldn’t utilize it right away because we don’t have the appropriate hardware. Even all of the computers in the world with their petaflops of computing power are too isolated with too much latency to think like a human in real time.

So let’s build something almost embarassingly simpler and more interconnected, and just give it to lots of programmers. A teraflops chip with a thousand cores running at 1 GHz with Erlang would only cost a few hundred dollars in large lots and bring supercomputing to the masses. Give it simple ways of interacting with the real world and let it start solving real problems. Maybe this completely sidesteps how to build R2D2. But I have faith that once we reach a critical mass of people, their needs will lead the way.

Short of that, maybe we can build virtual machines to simulate a thousand cores running at 1 MHz and at least play around with the math. It may not do much more than image recognition but it would get a whole generation thinking about solving problems in a new light.

There has been too much emphasis on correctness and exactness when researchers should really be focussing on charting boundaries so they can be smashed. This is more like imagineering than engineering and there are multiple routes that will get us there. I would very much like to work on a project like this, in fact it’s pretty much all I think about anymore. I wish so badly that I knew more people who were interested in this stuff, with the time, money and motivation to make it happen. I just have this gut feeling that it’s not as hard of a problem as people think. Arithmetic was hard before calculators, so now all we need is a calculator for thinking, or at the very least, finding needles in haystacks, because that’s most of what thinking is.

Comments

  1. zackarymorris posted this
blog comments powered by Disqus