Monday, June 30, 2003


A critical piece of human-computer interfaces is awareness, the ability of the human to know the state of a system. Most current software applications have a pretty linear model of attention: you're paying attention to the software like you're supposed to pay attention to the teacher in class. This is (in both cases) absurd: you've got plenty of other stuff on your mind. Because of this, awareness tends to be driven by interruption: think about the beep the indicates that you've got new email.

This is frustrating, though, because it's such a simple model, and it's so incredibly disruptive. As we start to use more and more collaborative systems, there will be a lot more for us to pay attention to. Actually, that's not quite the right thing to say: there will be more for us to be aware of. Awareness isn't really the same as attention, because my awareness of a process might take up only a tiny fraction of my attention. And my awareness might be quite intermittent.

There was an article in the New York Times a week ago about a new generation of devices that offered a non-interruptive awareness. I saw one of them at a Brookstone the other day. It's a globe that plugs into a phone line and changes color depending on how the stock market is doing. If the market's doing well, it glows green. If the market is down, it's red. (Of course the next generation ought to be tied to a specific portfolio.) This is great because the information, although quite unspecific and imprecise, is still filtering into your brain without causing interruption. It does this despite the fact that the information flow is effectively constant.

We need to develop a toolset of screen display interface widgets to convey awareness in a similar fashion. In fact, we need to think about a larger design space for awareness.

Wednesday, June 25, 2003

Software's role in Innovation

I'm beginning some research on the role that software plays in innovation or new product development. On the face of it, there are some obvious but fairly superficial ways that software might be employed. For example, CAD software is certainly central to the design of manufactured products; while the Boeing 777 made news for being the first all-digitally-designed plane, it seems impossible to imagine that any future planes, or anything as complicated, could be designed without the aid of CAD databases. Software also plays an important -- although still amorphous -- role in pharmaceutical drug research, as bioinformatics software datamines huge amounts of data for likely physiologic pathways or interesting chemical compounds.

But the broader, more interesting role of software in innovation, to me at least, is the potential that it has to serve as an intermediary between many different interests or stakeholders; innovation as an application of social software. For a new product to be successful, it must balance the interests of customers, both existing and potential, of manufacturing, of sales, of research and development, of strategists. With an enormous, multidimensional space of potential new product designs, software can serve a role both to explore this space and to help the many interest groups collectively navigate and find agreement.

Tuesday, June 24, 2003

The End of Enterprise Software?

It feels to me that we're close to a tipping point on enterprise software. While I do think that the various silver bullet solutions - .Net, J2EE, SunONE, grid computing, reflective middleware, computing-on-demand, web services, agent-based software, utility computing, application service providers, etc. - are mostly overhyped in general, I do think that taken as a whole, they do reflect the beginnings of a sea-change in how large companies obtain and use software. And that change has less to do with the nature of the software itself as it does with the way that software relates to other software.

In the old days, a new software installation was likely a greenfield installation - automating or monitoring an existing process that was previously handled manually. The software, it was hoped, would improve the ability of the enterprise to predict, monitor, and control this process, whether it was manufacturing, inventory management, purchasing, etc. As the trend continued, however, these pieces of software began to butt up next to each other; the purchasing system would need to send/get information to/from the accounting system, for example, or the sales system would need to update the inventory. This began the Dark Age of Enterprise Software, at least from the point of view of the customer. From the point of view of the big IT consulting shops, this was the Best of Times.

There's a couple ways to solve this problem, and one of them is to get an integrated package that does every single thing that your company wants done via software. This is basically Oracle's strategy, and similarly IBM and SAP. However, generally this trades off decreased inter-application integration costs for increased customization costs.

What's beginning to emerge, however, is the idea of a middleware bus, a way for many disparate applications to discover each other and dynamically send and receive data. Web services is one slice of this, but also a host of proprietary solutions put forth by startups; if you look at the VC deals being done, or the NIST or DARPA grants being given out, this receives a lot of attention. At first, this trend may make web-based solutions like a little less competitive, but eventually ASPs will catch on to the game and allow reflective and adapative integration as well.

This is good news for companies, although it won't arrive in a mature form for another few years. It's bad news, however, for the large system integration shops, as their jobs slowly but inexorably get automated away.

Monday, June 23, 2003

The Dual Nature of Biology

We -- meaning all of us software futurism geekoids -- often talk about borrowing inspiration, or more, from biology. This is a good idea, and I'm in favor of it, but I often think that people think it's going to be easier than it will be. Borrowing from nature is actually quite hard (I've recommended Steve Vogel's Cat's Paws and Catapults, haven't I?), and I think it will be even harder in software.

Here's one reason: in biology, every "component" (and of course that is a flawed metaphor) can serve many roles at once. Carrying nutrients and carrying away waste. Taking in oxygen and food. Sexual reproduction and waste elimination. It's even more true on a molecular scale. This seems to be a prime design technique in nature. Why? Partly it's just the slow-but-very-fine mill of evolution; partly it's the very nature of evolution starting with existing materials - it's easier, apparantly, to add a new function to an existing system than to evolve a new system.

Software, on the other hand, tends to be very singular: it is in fact considered a good design that each function has a single, authoritative point of responsibility. It would be an interesting experiment to try to write a piece of software where objects or components were required to have multiple independent functions.

Thursday, June 19, 2003

Finally, We Venture Into Politics

I promised in my first post that I'll try to steer clear of politics. I still mostly mean that, but we're doing some closer steering than usual today.

It's been in the news that Al Gore, among others, is interested in setting up a liberal alternative to the established, more conservative, cable outlets. While it's certainly true that the myth of liberal control of the media is long gone (consider that major media organizations are owned by GE and Rupert Murdoch), that doesn't mean that creating a liberal alternative is a good idea.

That's true for a bunch of reasons, but most are political so I won't mention them. And I can't necessarily say that it would fail, but the problem is that Fox News (oxymoron alert) succeeds because it serves a market. And Gore TV, or whatever, will only succeed if it can succeed as a business. I'm not so sure that there is an unserved market for liberals. They read the New York Times, listen to NPR, and watch the MacNeill News Hour. The problem isn't that liberals don't get liberal news, it's that no one else pays attention to it.

But this is a column about software (you've been very patient).

What the liberals have to do is abandon the whole idea of controlling big media (does anyone else remember the card game Illuminati?). They should be looking to social software. Instead of shaping public opinion, they should be worried more about mobilizing it. Blogs, IRC, chat, self-published web-sites, wikis - these are the ingredients of self-organized politics. There are plenty of pro-environment, pro-education, anti-theocracy, pro-conservation, anti-kleptocracy people out there; they just have lives. The sort of success with the Internet that Jesse Ventura had, and Howard Dean is currently having, and has made a difference in Korea, should be the rule, not the exception.

The Democrats lose because Republicans are more successful at mobilizing their core, fanatic, constituency. This will probably always be true due to the nature of the core issues (for example, the people that will benefit from opening up ANWR to oil exploration are far fewer in number than the people who will suffer, but they will benefit a whole lot more). What the Democrats need to be able to do is mobilize the non-core but still sympathetic population. MoveOn and MeetUp are going a long way towards doing this, but it's still a tiny minority of the overall population. The tools are almost all in place; all the Democrats have to do is stitch them together.

Concentrating the ownership of the media companies doesn't really stop the free exchange of information, but it does prevent the free exchange of informed opinion. And right now, that's what the Republic needs.

Wednesday, June 18, 2003

Whence UI Innovations?

I want to know when there's going to be some change in the standard graphics user interface. I am as big a fan of Alan Kay as anyone, but seriously, when he helped come up with the Windows-Icons-Menus-Pointer interface, Donald Rumsfeld was Secretary of Defense and Dick Cheney was in the White House. Uhh... you know what I mean. This was when machines ran at single-digits of Megahertz. Remember Megahertz? And they had Kilobytes of memory, and probably didn't have a hard drive. So why are we still using it? Yeah, we've got color, and spiffy pseudo-3D effects, and kind of cool roll-over glowing effects, but it's still the same metaphor, it's still the same toolset, and it's still the same basic idea.

For years, people have been saying that games are going to be a source of GUI innovation, presumably because there's so much competition in the gaming arena that there's no standard, and there's a lot of experimentation. Well, for one I haven't seen any cosmically different interfaces in games, and two and more importantly, I can't identify a single instance of a game-originating UI element that made it to the mainstream. (Though there was that Doom interface where you could kill processes.) This is not to say that there haven't been some excellent game UIs, and of course the PlayStation II and its ilk have given us a great deal of innovation in terms of the handheld controller (who could imagine two hands at once? Oh yeah, Doug Englebart did, thirty years ago).

And don't get me started on crappy handset UIs, especially phones.

I do have hope, though. The coming generation of cheap displays are going to plaster computer-driven images everywhere, especially in cars. And there's not a lot of real-estate left on the car dashboard, except...

Yeah, that's right. The windshield. Fighter pilots have been using heads-up displays for years. (Well, at least the F-15 simulator I used to play did. I assume the real thing did do, but I've never flown the real thing.) I think that passenger cars will have HUDs soon, and that means that we're going to need to develop a standard set of widgets, toolsets, metaphors, and conventions for displaying, manipulating, and interpreting overlay images.

The important part of this is transparency. I was excited to hear that Apple was introducing semitransparency for Aqua, but so far all I can tell is that's it's a special effect. Nice, but only a baby step. I want to see layers of information superimposed on reality.

And you know, it would make a great game interface.

Tuesday, June 17, 2003

Finishing about Halting

Okay, I promise that I'm done for now, and I'll talk about something, well, less terribly geeky tomorrow.

Well, a little less geeky.
Halting Steps

Here are some points made by Bruce MacLennan from the University of Tennesee, Knoxville, on why we shouldn't care about the Halting Problem, and why the Turing Machine is a broken metaphor for real life computing:

1. In real life, the issue isn't whether a computation will eventually halt, it's whether it will complete within acceptable time boundaries. If your brain needs to figure out what your eyes are looking at, it needs to do it in a fraction of a second. The "algorithm" it uses might be linear, or it might be superexponential, but it doesn't matter. Classic complexity theory ignores the constants, because analyses of performance are supposed to be independent of underlying hardware. Put another way, the algorithm is disembodied. But the real world is embodied.

2. The Halting Problem, and in fact the Turing Machine itself, is based on a computational model of exact answers. (There are in fact alternate models of the Turing Machine that return approximate answers.) But again, in real life, the issue isn't whether you get the exact answer, it's getting an approximation that's within an acceptable error range.

3. Inputs in the Turing Machine are exact symbols that represent atoms of meaning. But the real world is, well, real; that is, composed of real values. (This is unproven, but if it's discrete, it's discrete at an incredible fidelity, far beyond our mechanical embodiments of TMs. More on this later.) Not just real, but noisy.

4. The real world doesn't stop. Most processes in the real world are not just continuous, but continuing. Your brain doesn't stop figuring out what your eyes see once it recognizes someone; it just keeps on processing. There's really no equivalent of "halt" in natural computation.

MacLennan goes into great depth on these and other points.

Now, again, this is not to dismiss the importance of the Turing Machine, its relevance as a model of computation, or the intellectual achievement of Alan Turing in showing the limits of mechanical, embodied, computation. But it does show that as a metaphor, the Turing Machine is not well suited for describing "natural computation," the sorts of things that the real world does, and that embodied machines must be able to do as well.

And by the way, MacLennan lists four or five computational models capable of solving the Halting Problem.

Monday, June 16, 2003

Do Not Halt, Do Not Collect $200

Some thoughts on the Halting Problem.

For the uninitiated, the Halting Problem is the classic instance of a problem that a Turing Machine cannot solve. It's simple enough: given a description of a Turing Machine and an input, will that Turing Machine's program ever finish? ("Halt" is what stops a Turing Machine's program, kind of like END in BASIC.)

The algorithm to solve it is pretty simple:
1. Wait until it stops. If it does, then yes, it will finish.
2. If it doesn't finish, wait until it doesn't finish. Then it won't.

The hole in the logic should be apparant. By a clever proof that I am a little bit too lazy to reproduce here, it can be proved that Turing Machines cannot solve this problem for all inputs. (The proof is based on the idea of feeding the Turing Machine to itself.)

The first response should be that this is stupid. Anyone can tell, for a vast array of programs, whether it will terminate or

int a = 7;
int b = 9;
int c = a+b;
return c;

Does that halt? Yes.

int a;
for(int i=0; i<10; i++) {
return a;

Does that halt? Yes.

In fact, for many reasonable programs, we can determine in polynomial time whether it will halt or not (remember, by the rules of the halting problem, we also get the input).

The question that interests me is not so much whether, in the worst case, I can construct a Byzantine case that will stump the will-it-Halt algorithm, but for what classes of input it will succeed, what classes it will fail, and, yes, what classes it is indeterminate. And, yes, I can determine that for many, but obviously not all, inputs.

An helpful policy here is to construct an algorithm for Will-it-Halt with three legal outputs: Yes, No, and I don't know. The restrictions on the algorithm are that if it says Yes, then the input machine must definitely halt, and if the input is No, it must definitely not halt. However, it may return "I don't know" for cases that will, in fact, halt, or not.

You don't need to simulate a Turing Machine to realize it won't halt:

while(true) {
print("The spoon does not exist.");

All of you Turing fundamentalists can simulate that one, maybe that will stop you from complaining to me about my ignorance of computational complexity. The rest of us can move on.

The question shifts now not to analyzing algorithms, but analyzing input sets. Think of it as looking for vulnerabilities; there exists some attack that will crash my algorithm (or, more accurately, never crash my algorithm). The question is not whether I can prove it safe, because Godel and Turing are still right; I can't ever prove it safe because it isn't safe, and I can't detect the unsafe cases because my detector in turn is vulnerable. (Does anyone else remember that cool part of Godel, Escher, Bach with the exploding record players?) But I can begin to make generalizations about the stability of certain algorithms to certain inputs.

Having established all that, tomorrow I'll argue that the Halting Problem is irrelevant.

Friday, June 13, 2003

More on Turing Completeness

Here's the thing that gets me. Proving something Turing complete is saying that it's at least as powerful as the Turing Machine. So let's say that all of our computers were finite automata, and then we discovered a Turing Machine in a ditch somewhere. It's like we ran an automaton program on it, proved it was "automata complete," and then never worried about all those pesky tapes and reading and writing.

Absurd, right? But that's exactly what we've done with DNA. DNA is an amazing thing. It "executes" (obviously this is a flawed metaphor) every base in parallel, simultaneously activating and inhibiting other stretches of the gene. Does that sound like a Turing Machine? It most certainly does not! But because some fairly bright people figured out how to simulate a TM with DNA, the story seems to have ended.

By the way, I've revised yesterday's entry slightly because on rereading it I noticed that it wasn't particularly clear on a couple of points. Absorbtion blog in action.

Thursday, June 12, 2003

Turing Fundamentalists

Revised June 13

What's the deal with people defending the Turing Machine? This seems to come up everywhere: at the O'Reilly ETech conference, on the Coherence Engine discussion board, on a Boing Boing discussion board a year or so ago. Whenever anyone mentions the possibility that there might be a more powerful model than the Turing Machine, people go nuts. I usually get accused of not understanding the abstraction. Well, that might be true, although my old computational complexity professor would be disappointed to hear that. But the fact is that the Turing Machine is mostly certainly not the most powerful model out there.

This is, however, a complicated question. Let's break it into pieces. First, there's the issue of whether a computational model can, in any amount of time, solve a certain problem. Recall that it was Turing's proof that there are problems that the Turing machine cannot solve, notably the Halting Problem. This is an extension of Godel's incompleteness principle. Keep this in mind: Turing's accomplishment was not showing the universality of the machine, although he did do that; it was in showing the fundamental limits of it.

Now even given two models that can solve a problem, there's still performance questions. This isn't a trivial difference; a model that can solve a problem in polynomial time really is fundamentally more powerful than one that takes exponential time. And there are tons of complexity classes that describe computational models that solve problems in polynomial time that it would take a standard deterministic TM exponential time. Just for one example, if a DTM can call upon an oracle to answer questions, it can outperform a standard DTM. And of course DNA computers can solve NP problems in linear time, although requiring exponential space.

There seems to be debate in the complexity field over whether quantum computers will be a more powerful class than deterministic Turing Machines. The complexity class in question is BQP, for "bounded quantum in polynomial time." Is BQP a proper superset of P, meaning that there are problems that a quantum TM could compute in polynomial time that a DTM couldn't? Even more provocatively, it's possible that a quantum computer could compute problems non-computable (obviously we are dancing dangerously here with the word "compute," however) by any Turing Machine.

This is a field of study known as hypercomputation, that studies computational models more powerful than the Turing Machine, including, yes, believe it or not you skeptics, models that could solve the Halting Problem. It's a sketchy field as yet, but it's real; there are publications and workshops and proceedings and everything. I'm going to work through the field and blog it as I go; I'm still at the lit review stage.

But there's a social question buried here. Why are people so freaked out and defensive that there might be a more powerful model? I think perhaps people have taken "universal" the wrong way. Turing didn't prove the universality of the Turing Machine; he proved that a) a single Universal Turing Machine can simulate all other Turing Machines and b) the Turing Machine model was equivalent to a number of mechanical algorithms for solving problems. But this really is a bit of a circular argument: our definition of "computation" is "the thing that a Turing Machine does," so of course Turing Machines can do anything that's computation.

The open question is whether there are ways to solve problems that cannot be specified in the mechanical algorithm fashion of Turing Machines. And the signs are that there almost certainly are.

Wednesday, June 11, 2003

Computational Narrative

What's the intersection of narrative and software? Narrative -- the ancient idea that stories are structured by elements such as protagonist, conflict, the Aristotelian three-act structure, or the Campbellian Hero's Journey -- would on its face seem to have little to do with software. But I think there's great potential to combine the two and see what comes out. This could be applied in many ways:

Can computers create narrative? There have been lots of experiments with computers creating various arts: painting, poetry, text. If something like the Three-Act Structure or the Hero's Journey is really a template, then is it possible to program a computer to fill in that template in a way that is still original? It's clearly possible to write a program that produces one of a finite set of options, but even a tightly constrained template like the Hollywood Three-Act Structure can support infinite stories (not that you'd know, but that's another

Can narrative be a part of the user interface? We grow up on narrative; almost everything we encounter is in some way a tiny story of a protagonist achieving an important goal over difficult odds. News stories, commercials, books, movies, all media are saturated with it. In contrast, our user interface experience is deathly dull, a monotony of stimulus and response. If it felt more like the Hero's Journey, perhaps it would be more compelling, and indeed more intuitive since we can all speak this language.

Can software support narrative? Online games like Ultima Online or Everquest are all the rage, but as far as I can tell from the outside (I've never played them), they are sadly lacking in true narrative. They do seem to have a sort of stunted conflict: you go out, you camp, you kill a monster, but that's hardly satisfying on a deep level. I'm not necessarily talking about computer-created narratives, although clearly for massively multiplayer games you need some sort of computational intervention, but simply the idea that software can be a narrative medium as powerful as film or television. Indeed, it has the potential to be much more so, as it is so much more customized, interactive, immersive, and social. So why are the narrative options offered so paltry?

Wednesday, June 04, 2003

Whither Debugging?

Went to an interesting talk today by David Levine, formerly of Analog Devices, among other places. His interest is in how you use source-level debuggers for highly optimized code, or, in other words, what you do when you compile with -O and -g at the same time.

The problem, briefly, is that the sorts of things you want to do with a debugger -- set breakpoints, print the values of variables, set the values of variables, set watches, etc. -- become extremely difficult in highly optimized programs. As the optimizer works, it is moving code around, possibly removing it, using the same memory location for two variables, etc. A "breakpoint" that you set may correspond to no single valid point in the code by the time the optimizer is done. In fact, a variable that you think has a value at that point may already be overwritten by something completely different. This is especially true for optimizations like loop unrolling, code hoisting, and common subexpression elimination.

The traditional solution, he points out, is to debug heavily with optimization turned off. But that's silly for a couple reasons. One, you really ought to debug the optimized version if you're planning on using it. Two, the optimized version might be necessary to run the program correctly, for example if timing (such as in a DSP) or footprint (if it is supposed to run in an embedded device) are issues.

It was a neat talk and he had some interesting suggestions, but I disagree with some of his basic assumptions. It seems that underneath it all, he's making an implicit claim that lines of code should be treated like transactions - atomic, consistent, independent, durable. And the point of forcing debuggers and optimizers to co-exist is to preserve these properties. I say, faugh! The ACIDity of lines of code is an illusion. It always was, and especially with superscalar multiple dispatch speculative executing hardware, it's even more of an illusion now. The right answer is not to scrabble with our fingernails to preserve this, but to abandon it and move on.

This begs a more important and fundamental question, which is how do we debug programs for which we do not have entirely reliable source? Highly optimized code is only one instance of this; another is automatically generated code (for example by biological processes). As Caltech's John Doyle is fond of pointing out, if we can't figure out how to debug this stuff (or to prove it safe and correct), then civilization is liable to end. Once we move completely into the Media Lab future where everything is networked and running on embedded chips, we become extraordinarily vulnerable to system errors. And it will be very hard to reboot the world, so we better either get it perfect the first time or have a strong capability to debug it in real time. This will become even more difficult as we start running into higher order emergent behaviors.

Tuesday, June 03, 2003

Attention-Deficit Hypertext Disorder

Blogs are, by their nature, fast-twitch brain cells at work. I have an idea, bam, it's up on your screen. There's no technological reason for this, of course, but it's the social nature of the beast. The problem with this is not that ideas aren't well-thought out (although they aren't), or that they don't benefit from a bottleneck editorial process that ensures quality (although they don't), but something worse: they never change.

Blogs represent a great deal of knowledge, insight, and personality, but the problem is that they grow the way crystals grow: always outward, only at the edge. A blog represents a time-ordered series of thoughts, which admittedly is an incredibly powerful way to put your thoughts in order. After all, you thought of them in that order, why shouldn't a reader? But this is the same fallacy that inhabits biology textbooks that insist on presenting Lamarck before introducing Darwin; just because a (wrong) idea came first, doesn't mean the best way to learn the subject is to repeat the mistakes of the past.

It's best to think of blogs in two dimensions: one is the ordering of publication; this is the standard that all blogs are today. But the second is the order of comprehension, the best way to read and understand it. Now in many cases that might be the same as, or largely similar to, publication order. But what if I decide I was wrong about an earlier post? What if my insights have changed? What if I decide that the whole "hammer equivalence" is a dumb idea and I should have used the "Six Men of Indostan"? Someone who reads in publication order will not benefit from my hindsight.

So I'd like to borrow an idea from operating systems, something called an absorbtion log. Let's call it an absorbtion blog (not the same as a self-absorbtion blog, of which less said the better.) The idea is that as new ideas are appended to the log, they can overwrite and replace older versions of that same thought. (In the OS version, the log entries can delete older values of the same variable. This improves the speed of replay of the log in case of a crash.) And really, we don't want to delete the old entry, just string it off in another dimension, so that readers can, if so inclined, discover the stages of thought in the past. I've seen a few cases of integrated wikis and blogs, and it seems that this is a good step towards absorbtion blogs.

The fundamental question we should attempt to answer is how do we make representations of knowledge -- such as blogs, wikis, The Brain, knowledge management systems, libraries, encyclopedias, etc. -- provide three competing services: a graceful way for new readers to learn the content; a way for experienced users to find new information; and a way to encourage growth not just at the edges (temporal or otherwise), but organically throughout the system.