keeping simple

Despite some deep results, algebraic automata theory has fallen out of favor in theoretical computer science. Reasons include the disciplines failings such as a love of over-generality, weak mathematical background of people working on “formal methods”, and gap between theoreticians and engineers. But perhaps the key reason is that traditional state machine presentations in terms of state sets and transition maps are awkward and carry too much irrelevant information.

The standard presentation of a Moore machine is  M=(A,X,S,st,δ,γ)  where  “A” is the alphabet of events, “X” is the set of outputs, “st” is the start state,  δ:S x A→ S is the transition function and γ:S → X is the output function.  But  we really don’t care about the state set in all but the simplest state machines. Interesting systems have ridiculously large numbers of states.  Names of states don’t matter.  Extra states don’t matter. Suppose “s” is an element of “S” that is unreachable – no sequence of inputs will drive M to “s” from “st”. In that case what difference does removing “s” from “S” make? Or suppose s and s’ are both reachable but not only is γ(s)=γ(s’) but for any sequence of inputs that can drive the machine from s to a new state, the output of that new state is identical to the output of the state reached by following the same sequence of inputs from s’.  In that case, we could simplify S and δ by removing one of the duplicative states and merging paths.

What’s more interesting is to consider what output a Moore machine will produce from a sequence of inputs: thinking of the Moore machine as a map from input strings to outputs. This is  a function that can be constructed by primitive recursion on strings.  First, extend δ to strings to define a new function Δ. The   empty string that has zero length doesn’t cause any state change Δ(s,empty)=s   and if “w” is a string and “wa” is the string obtained by appending “a” to “w”, then Δ(s,wa)= δ(Δ(s,w),a).  Define  M*(w) = γ(Δ(st,w)). The idea is that M*(w) is the output produced by M in the state reached by following “w” from the initial state.  If you look at M* you see it contains all the interesting information in M -  because the names of states and unreachable states and duplicate states are not interesting. In fact in the 1950s Myhill and Nerode described how to generate a state machine (not necessarily a finite state one) from any function on the set of strings over an alphabet.

These functions are much more useful in describing complex state systems than are Moore machines – not least because they can be partially specified when we don’t know or care about all the possible behaviors of the system and because they can be composed in a way to represent any interconnection.

In the next post, I’m going to discuss composition of message passing processes and compare to the “formal methods” approach which is based on the incorrect assumption that automata need to be “enhanced” in some way and that replaces automata with things that have very little mathematical structure at all.

All the papers and talk references have moved to a new page

The newest paper summarizes the recursive function approach to state machines and composition of state machines and is called primitive recursion and state machines.

My graduate school research was motivated by a difficulty we have doing real creative engineering in operating systems that may seem ridiculous to people who don’t work in the field. The problem is that we can’t describe the problem. What an operating system does is complicated beyond the expressive capability of the mathematics we have at hand so we end up with vague gesturing, making applications work, and commitments to support existing APIs which are themselves mostly defined by what existing implementations do.  One result is that there are embarrassing errors in nearly every commercial OS. Another result is that OS development has stagnated. Compare to databases where at least the relational algebra idea has allowed researchers to think about what the damn thing is supposed to do at some reasonable level of abstraction.  Formal methods research has produced nearly nothing of use to engineers – the only useful parts have been the automated validation programs and those have advanced mostly because of the increasing power of the machines used to run the validation algorithms. All this by way of introducing another attempt to clarify the primitive recursive basis of compositional state machine theory.

Download here. (updated to improve fonts!)

Applications paper on the unfortunately acronymed Proportional Integral Derivative controllers on the way.

And like Intel, I would argue that mobile software companies are instrumental in making silicon solutions pervasive, because they tick two major check boxes: reference design and support.

The hidden asset of mobile software companies
Mobile embedded software companies (e.g. Myriad, Access, Aplix, NXP software, Azingo) have a unique understanding of products as a hardware/software system. They understand how silicon can be leveraged, encapsulated and productised to fast-track device delivery. Beyond specific IP, these companies have the capability to build the very first product that will feature a new chipset. This is the reference design check box.

A reference design is not a half-baked breadboard; it is a scale 1:1 device, ready to ship.

The absence of such capability has drained Texas Instrument, once the mobile silicon leader. Alternatively, true reference design has been instrumental in the success of Qualcomm and Mediatek.(cite)

Also see previous note

This is a brilliant idea.

Most innovation, well, isn’t: it is “unnovation,” or innovation that fails to create authentic, meaningful value. The biggest stumbling block to innovation is unnovation: most companies are too busy unnovating to ever learn how to truly innovate.

In the race to innovate, most organizations forget a simple but fundamental economic truth. A new process, product, service, business design, or strategy can only be described as an innovation if it results in (or is the result of) authentic, durable economic gains.

Unfortunately, much of what our economy produces today isn’t innovative — it’s unnovative. The evidence is hard to dispute: we merely need to note how deep the global decline is, how consistently 20th Century business fails to do stuff that matters — or just how many industries are caught simultaneously in deep crisis.

Here are some examples of unnovation.

The Hummer was a product unnovation, which destroyed value for both society and Detroit.

CDOs were a financial unnovation, that crippled the financial system, and have cost everyone hundreds of billions.

Integrating into auto finance was a business design unnovation for Detroit — one which diluted and sapped the incentives to make authentically innovative cars.

In our field, innovation requires investment and time. But “unnovation”! That’s a different story.

If anything, Wind River’s inability to breakout, despite a once Microsoft-like position of dominance, is a by-product of their failure to meaningfully go “up the stack” and away from their historical focus on the silicon layer as a primary differentiation point.

In other words, if Wind River had enabled the next generation of Cisco and Apple killers by providing more differentiated OEM-in-a-Box offerings, ala what Google is now trying to do with Android, they would not be staring at a $900M market cap and relatively flat revenues, margins and stock price.

Well, that’s an argument. Embedded is a tough beat, but Wind did not exactly set the world on fire developing new concepts and software. Intel’s history in software is not glorious either – so it’s going to be an interesting challenge for the new entity.

I have also learned something about my country. I run a global company, but I am a citizen of the U.S. I believe that a popular, thirty-year notion that the U.S. can evolve from being a technology and manufacturing leader to a service leader is just wrong. In the end, this philosophy transformed the financial services industry from one that supported commerce to a complex trading market that operated outside the economy. Real engineering was traded for financial engineering. In the end, our businesses, our government, and many local leaders lost sight of what makes a nation great: a passion for innovation.

To this end, we need an educational system that inspires hard work, discipline, and creative thinking. The ability to innovate must be valued again. We must discover new technologies and develop a productive manufacturing base. Our trade deficit is a sign of real weakness and we must reduce our debt to the world. GE will always invest to win globally, but this should include a preeminent position in a strong U.S.

Jeff Immelt

The idea of  the CEO of GE writing such a thing 2 years ago would have been unthinkable.

Data on the overhead of virtualization is hard to come by. Rackable proposes an interesting alternative that they call physicalization. I wonder whether the CPU is the most important resource to multiplex and I remain totally puzzled by the motivation of Intel/AMD in this area.

Irving Wladawsky-Berger started working at IBM in 1970 and retired in 2007 with what is, to me, the smartest corporate response to Linux/OpenSource as his capstone accomplishment.

TG: Sun has committed to releasing all of its code as open source. Do you think IBM will do the same?

IW-B: I don’t think so, because I honestly don’t think everybody wants to see all your code. Remember, the key to open source is not the ability to see the open software, it’s the forming of a community around it that will participate in its development and its maintenance.

You cannot go in your closet and look for old code and throw it out there and tell people to form a community around it. They may say, Irving, that’s legacy code that we have zero interest in working on. We continue to open source quite a bit of code, but we are fairly selective, and we work very closely with communities to decide whether to open source or not. (Guardian)

I think this second paragraph is misdirection, but nicely done – the highly paid corporate officers at Sun watched that zip over the plate, get caught, called strike, and tossed back to the pitcher before swinging wildly and falling over. More interesting, Wladawsky-Berger is thinking about the structure of corporations and the changes of the last 50 years.

The whole relationship between individuals and corporations started to change around twenty years ago because the old ways no longer worked.  Innovation and creativity are now needed more than ever in order to keep up with a continuing stream of technology and market changes.  Enterprises have had to become much more flexible and dynamic in order to survive the intense competition they started to face from companies around the world, large and small.  To do so, they have had to embrace a lot of the innovative entrepreneurship culture pioneered by VC’s and start-ups.

Similarly, individuals can no longer assume that just being loyal to a company will translate into a stable, orderly, life-long employment.  They are responsible for their own careers, and have to look out for their own opportunities. No matter how great a business they work for, they can no longer just rely on the company to take care of them.  Such a culture has much more in common with an entrepreneurial form of capitalism than with the corporate capitalism William Whyte wrote about.

This seems true and perceptive, as far as it goes. But if you read the blog of people at the other end of IBM’s changing business model you get another sense. “Entrepreneur” starts to sound a lot more like  Dickens and a lot less like Serge and Larry make a cool company.  The old corporate model depended on a social contract, that was stultifying, but the new model seems to me to depend on an unsustainable asymetrism of loyalties.  I wonder what Wladawsky-Berger really thinks of the stultifying and terrifying evaluation metrics that keep the company’s workers in line as the nimble behemoth sheds its high paid US staff.  One does not have to be in the grips of a nostalgia for the “organization man” days to wonder about the sustainability of a company that openly tells its workers and host communities that there is no social compact at all.

Digital Equipment Corporation
Silicon Graphics Corporation
Sun Microsystems

One might get the impression that the boards of directors of technology companies have as much ability to intervene to stop suicidal business strategies as the boards of directors of Bear Stearns did.

But business is simple: you always have to look at the business model of the company and of the company management and other employees. In the case of Sun, there has been zero incentive for Sun management to bring in people who would challenge their decisions or the lax process and culture at the company. They get paid, feted, and admired by flunkies without being forced to actually justify their poor results. In the case of the banks, if your management staff and other high executives have the chance to make hundreds of millions of dollars personally by taking crazy risks with other people’s money, what would you expect? One of the things that I find most ludicrous about economics is the implicit theory that corporate employees identify their interests with the interests of the company: only engineers are stupid enough to do that. Once you realize there is a difference between the business model of the company and the business model of the people who run or invest in the company, the underlying logic of all sorts of wacky strategies that leave upper management well rewarded become clear. I used to be puzzled by well financed startups and public companies that motored along, getting new investment or other financing, being cheered on the street, and so on without having any remote chance of ever making any money. But there are plenty of opportunities for the people who manage, advise, and lend and invest other people’s money to all personally do well from such a business.