copyright notice
To the Editor:
Peter Wegner has thoughtfully argued that interactive computing is an inherently more powerful computational paradigm than algorithmic computing. In so doing, Wegner has creatively and vigorously reinforced the experimental evidence in computer science that the behavior of sufficiently robust, interactive systems cannot be defined algorithmically.
One fallout from his piece may be greater self-confidence of experimentalists worldwide as they shed their guilt over their inability to document the behavior and complexity of the systems they design and implement. Computing experimentalists have intuitively felt, but were timid about broadcasting, that an attempt to provide formal models of their systems was unrealistic. Wegner goes one step further. He argues that "proving correctness of interactive [computing systems] is not merely difficult but impossible." Wegner's article may give "good enough computing" a legitimacy and dignity heretofore unimagined. A positive spinoff of this might be that computer scientists could become as concerned with the interactive and participatory aspects of program semantics as they are with algorithmics, and that nonformal software engineering foundations for embedded systems, objects, and programming and the large will become respectable.
Wegner's argument that algorithmic computing is weaker than interactive computing is compelling. In addition to his formal arguments showing that interaction machines cannot be expressed by Turing machines and his incompleteness proof that interactive systems cannot be expressed by fist-order logic, there are several practical examples showing that interactive services like banking or airline reservation cannot inherently be realized by noninteractive (Turing machine) systems.
Another example is the "year 2000" problem with PCs, or the "elapsed time since 1/1/1970" problem for Unix. In this case, computer users (both physical and digital) take each observation of correct system date reported as a confirming instance of the hypothesis that the system always has the correct date. Formally, the hypothesis would be something like "the contents of the CX register after performing function 42 of interrupt 21" is equal to "the current year." What the year 2000 problem shows is that correct time observations were not confirming instances of this hypothesis at all, but rather one where both terms were temporally qualified (e.g., "on or before 2000). Most experimental computing is predicated on the fact that successful runs confirm correctness - this isn't always true even in hardware.
These sorts of problems exist in all complex interactive environments. Some, like those above, may be a result of incorrect software interpretations of hardware. Most, however, will be a result of semantic confusions engendered within software systems such as non-monotonic code expansion and confusing extensional and intensional equivalence among variables.
But, as Wegner observes, the larger issue has to do with the essence of embedded and reactive systems which provide continual services over time. This computational metaphor has even become standard for mundane office productivity applications.
Perhaps Wegner's work will form the foundation for new and more effective models of software technology that account for both algorithmic inner behavior and interactive collaborative behavior of software systems and their components.
Hal Berghel
berghel.net