"Compare inventing a game -- inventing language -- inventing a machine." (L. Wittgenstein, Zettel) In what follows, I intend to do just that. In the end, I hope to declare the mathematician/essayist Gian- Carlo Rota to be right: when computer science finally decides to be honest about her foundations, Ludwig Wittgenstein will be vindicated (G.C. Rota, Indiscrete Thoughts). Computations are, after all, rule-followings. But first, the question is simply where one finds the foundations of computing.

Alan Turing and Alonzo Church are canonically held to be at the foundation. Computing is about algorithms. Algorithms are essentially Turing machines, infinite storage and finite control, sequential, state-transition specifications. The important thing about Turing machines, says tradition, is their essential equivalence to a class of recursive functions. The theory of computability is really the mathematics of the natural numbers and finite mathematical induction.

As the discipline of computing has matured, mathematical reductionism has grown more onerous. The celebrated idea of Edsger Dijkstra is that a program just is a function transforming inputs to outputs. Programs are just cleverly compressed tables of logarithms, no matter how fancy they pretend to be. This idea is rerun when the denotational semantics of a program are given: here, a mathematical function is produced which represents the program. This function is produced compositionally, from the functions said to denote the program's primitive components. The meaning of the program is taken to be the transforming effect that it has, regardless of how the program specifies the transformation be performed (for example, regardless of how quickly, with how much space, how much synchronization, and how much communication).

In retrospect, all of the mathematically reductionist works on the "foundation" for computing are self-eliminating. They all treat computation by describing its non-computational effects (in the same way that semantics eliminates the essential features of syntax). They approach computation by describing snapshots of the world before and after computations. By ignoring the central phenomena, the process of computing and the specification of a program, they miss the point. They fail as foundations and will soon enough be regarded merely as bridging theories between two distinct paradigms.

Amazingly, computer science thought her foundations secure for at least three decades as the self-described "theoreticians" of computing unearthed the complexity hierarchies and dreamed of proving P not to be NP. Turing-computability, Turing- or RAM-complexity, and the semantics of programs are the three accepted forms of identification for a theoretical computer scientist.

Then Peter Wegner, before his naked emperor, had the temerity to announce that algorithms are not what most of computing is about. Instead, the management of interaction better describes in abstract the day-to-day computing practice. It is as scandalous as the observation that scientists do not follow scientific method, or that economic behaviors are neither Bayesian nor utilitarian, or that logic is about notation, not reasoning. There is no disputing the observation. The fact is that there is more interaction than transformation on automata today. All that remains is to understand clearly what the difference is and how the century-old logico-mathematical legacy went wrong.

An algorithm is a specification of how a transformation is to happen. It is not really a specification of what the transformation is, that is, to what mathematical function the transformation amounts. An algorithm is a recipe for transforming. As a recipe, it presupposes a rule-following architecture, system, or device that can bring about transformation. As a specification, it exhibits a degree of detail or a level of abstraction. One way of saying how something happens is to reduce it to smaller constituent or component happenings, its parts. One way to create subparts is to sequence the parts in time. One could imagine equally well a spatial decomposition of a system's complex operation. The instructions for infantrymen deployed in a line spatially decompose an algorithm of engagement. Any graphical user interface is a spatially decomposed specification. Traditionally, though, one thinks of temporally juxtaposing durationally smaller subparts. Hence, an algorithm gives step-by-step instructions for a temporal process: long division, Euclid's greatest-common-divisor, fast-Fourier transform, finding the shortest path in a graph, step one, step two, and step three (perhaps with coda), the minuet, the way to soup. A computation is the following of an algorithm that governs a process in time, animated solely by the rule-following.

This is the received view. On this view, concurrent or multi-processor distributed algorithms are specifications that do not specify the exact interleavings of some actions. Non-deterministic algorithms denote sets of functions. They are really just mathematical abstractions for discussing the possibility of transformation. Probabilistic algorithms are a class of transformations that admit among their inputs the outcomes of chance and pseudo-chance events.

Algorithms are said to have inputs and outputs, though Turing machines that generate recursively enumerable sets have no input and have infinite outputs. In any case, the input is fixed and complete before the algorithm completes, usually in fact, before the algorithm begins. Successful algorithms terminate on their input, or else continue to produce meaningful output. A program that merely exercises a machine, or busies a rule-follower, that generates heat in the device but no information in the model, is a pathological algorithm. Algorithms are goal-directed. They have goals of production: to produce a decision, to produce an output value or output data.

There is a distinction between the algorithm and an execution of the algorithm on particular inputs. Normally this is no more than the difference between f(x) and f(a), between potential transformation and actual transformation. In the case of distributed and probabilistic algorithms, an execution of the algorithm actually completes the algorithmic specification, either of the process (supplying the interleavings), or the input (supplying the chance events).

Algorithms are said to have implementations. One may implement bubble-sorting with array data structures, in a dialect of the LISP programming language, with multiple threads of sequential control, and on a Alpha architecture running a UNIX operating system. There can be many distinct implementations, multiple tokenings of a type, and many subtypes of subtypes. Algorithms may have novel implementations, due to the multiple-instantiability of the information model and of the symbolic data. Thus, one may perform binary arithmetic on just the upper row of an abacus (a deliberate discordance of number systems), or on a collection of laptop computers arranged in a row (opening and closing the lids to represent ones and zeroes). It is of course the great modern discovery that there are devices with causal properties that can be marshalled so as to automate rule-following for arbitrary sets of rules at arbitrary times. Elective rule-following upon sticks and stones, pencil marks on paper, and abaci, is lesser engineering but no smaller an intellectual achievement. Elective algorithmic computation is perfectly good algorithmic computation, so long as one elects to follow the algorithm.

Algorithms suppose primitive operations, a floor of atomic instructions. By implementing, the floor is lowered and detail supplied (though this story of supervenience must be more complicated than anyone imagines: when are two algorithms identical? When is a putative implementation actually a different algorithm? Is it not better to talk of an algorithmic stance instrumentally taken?). As specificatons, refinements are possible: explanations of explanations; prescriptions for prescriptions.

Peter Wegner's claim is that algorithms do not suffice to capture what we mean by computing. Lots of computing takes place across algorithms, and takes a more general form than transformation. A programmed interaction is at best a connected collection of algorithmic experiences.

Some interactions are patchworks of rule-followings. Even when there is rule-following, the result is not always a transformation. In the interstices between transformations, the inputs of one algorithm typically depend on the outputs of another. This dependence is not specified algorithmically, not as a function, not even as a set of functions. The dependence is specified to be there, but is not identified. It might be a vaguely described dependence, described in a way that is incommensurable with the algorithmic description (or at least with its level of detail). The rules say that things happen, but are not able or willing to say how. Who or what connects one rule-governed process to the next? It is not modeled with respect to a device. Maybe it is something, such as the user of a computer system, the agency or free will of which is best respected. Maybe it is a physical process best described in terms of state variables unadopted by the informational stance or unmet by the information model's ontology. Maybe it is another computer, the algorithm of which is unknown.

For there to be interaction, there must be at least two things interacting. One may program parts of their interaction. There may be one program interacting with some agent or environment, or two programs interacting in a loosely coupled manner. There may be two agents interacting according to a protocol. A protocol is a kind of program.

Wegner gives driving as an example of paradigmatic interaction. It is an interaction of a driver with a traffic environment. The inputs to the driving at any time depend on what the driving has thus far amounted to. If the driving is automated (and the road conditions varying), then the driving is interactive computation (upon a stream of input traffic that the driving co-creates).

Any control system is a programmed interacton. A thermostat maintains a relationship with its environment in a rule-governed way. A control function over a controllable subspace (for example, a plan for missile guidance) is simultaneously a spatial and temporal decomposition of a complex rule for behavior. Historically, most of control theory is about decomposing functions into subfunctions rather than decomposing algorithms into subalgorithms. But computing makes possible the latter different view. As soon as one admits the designed device into the discussion of control, one begins conceiving of the rules specifying the control as they are implemented on the device, not just the mathematical abstraction of states and programmed state-transitions. Avionics are said to do computations as well as to apply their controls. The postnatus of computing parts implementation from its mathematical abstraction.

A familiar example of programmed interaction is interactive text editing. Between each keystroke, the computer dutifully executes the appropriate algorithm upon the data as it finds them. Connecting the keystrokes is the decision-making which converts the result of the last input into the next input. The user of the system includes the current state of the text in the decision of what to do next. Instead of saying that there was a series of algorithmic computations, one says that there was an interaction. (One may use an interactive editor in a non-interactive way, for example, when the input is scripted; one may also drive with closed eyes and stone hands. One may learn without asking questions. But an interactive system primarily functions interactively.)

A second example is an operating system, which receives inputs over time, such as requests, events, and resources, while doing things such as scheduling, distributing, and communicating. Instead of saying that operating systems do their work by stringing together lots of little computations, each appropriate to a situation that the operating system partly created, we say that computing includes the work of operating systems, the interactions between programs, resources, jobs, and users.

A third example is cooperative search distributed on two processors communicating by passing messages. As each "sequential process" discovers something interesting or exhausts some subspace, it communicates that fact, interacting with its interactor, which reacts to this new input. The timing of messages is not predicted by the specification of the distributed program. Each of the interactors executes algorithmically between receipt and transmission of a message, but their joint effect is not well captured as a transformation upon input specified independently of the transforming algorithm.

If there have been some algorithms executed, A(0), ..., A(n), each transforming input to output, I(i) to O(i),

	   ---  A(0) --->            ---  A(1) --->
	   |             |           |             |

	I(0)              O(0) --> I(1)             O(1) --> ...

and if

	I(i') = f(O(i)),

then there is no knowing or stating f, even though it is part of the system and part of the computation. One might further say that the indeterminacy is due to an unknowing of events, not an ignorance of transformations; thus, I(i') could be obtained from O(i) through a specifiable function g(), which is known, but conditioned by unknown events E(i):

	I(i') = g(O(i), E(i)).  

To press the algorithmic view is to call the interaction a transformation on the total input

	( I(0), E(0), ..., E(n) ),

an object which is not complete until (just before) the computation completes. Theoretical computer scientists will call this an extreme case of an on-line algorithm, an algorithm that does not have all of its input before it begins. Wegner and I would call on-line algorithms degenerate interactions.

Like algorithms, programmed interactions are goal-directed. They have maintenance, achievement, or progress goals, not just goals of production. Production is a kind of achievement, but there are clearly achievements that are not productions. Achieving balance or synchronization does not produce something that can be called output. Unlike algorithms, the responsibility for the output does not lie solely with the input and the program. Blame and credit rest with the interactors, their interaction, and the inputs that they co-create.

In the algorithm-following picture, the input is outside of the algorithm, hence separate from the study of the mechanism. Computation occurs on data, which are grist for the mill. In the picture of computation-as-interaction, computation occurs with data, which are its collaborators. The data and whatever connects the data or supplies the data are part of the system. The total system is not mechanical in the sense of being fully automated, but it is still programmed in the sense of being entirely conceived and designed.

One says that the editing session corrected the document over time; it did not just take time to transform the unedited text into the edited text. The user performed an interactive computation with the editor. And vice versa, the editor interactively computed the changes with the user. We shall return to the question of what should be the restrictions on calling something a computation. Clearly the connotation of deterministic automation must be stripped away before one can imagine computation to include the results of more general forms of process specification.

By considering a larger system that includes non-algorithmic components, there can be reference to persistent entities: users, namespaces, data and process objects, services, resources, configurations, intentions. The core activity of computation in practice has come to mean the design and management, the specification of operation and of interoperation, of those persistent entities, not just the ways they can undergo transformation. The algorithmic description is inadequate. Wegner's perception of this is due to his understanding of the object-oriented paradigm for program design, according to which programs are specified as if they were operating systems. Objects act upon each other as if they were members of electronic societies engaged in a nexus of information transactions (very much like Marvin Minsky's idea of the mind as a society of homunculi). A program defines a system in terms of its persistent interacting subsystems. This is in contrast with John von Neumann's procedural paradigm according to which programs are written by composing small transient transformations into larger and longer transformations, as if every rule were a shorthand for a sequence of yet more rules. Programming can be gossip-regulating, not just pyramid-building.

Note that many interactions become transformations when the interacting parts can be described algorithmically (for example when the editor takes its commands from an automaton, and there are no important environmental considerations). Even then, it may still be useful to resist the claim that the whole system is an algorithm and to insist on the recognition of the distinctive interactive structure of the aggregate transformation. It may be good modeling, good design, or good science to take the interactive stance.

My special concern is the relation between argument games and logics, between interactions and algorithms in the context of rational belief.

Games are specifications of special kinds of programmed interactions: interactions with bilateral agency. The objective of a game is to construct an outcome from the play, an output upon mutually dependent inputs. Algorithmic transformations mediate the game, but the players are said to be following the rules of the game.

For discrete two-player games with non-simultaneous movement, there are two distinct input streams, X(i) and Y(i), and states of the game S(0), T(0), S(1), T(1), ..., S(n), T(n) with pairs of plies per game turn. Each state can be computed from the preceding state and the player's move:

	T(i) = f( S(i), X(i) );

	S(i') = g( T(i), Y(i) ).

Players respond with their moves; they have access to S(i) or T(i), not just to S(0). Here, f and g must be algorithmic and might as well be functions. (Think of the accounting in each Monopoly turn.) Parts of the dependence of X(i) on S(i) and Y(i) on T(i) might also be algorithmic: there might be a protocol that play must follow. But the dependence cannot be completely specified because the possibility of choosing a move is essential to the conception of the process as a game. There are no functions a and b that give X(i) = a(S(i)) or Y(i) = b(T(i)) unless the players are really deterministic automata. If one player is specified, the game could be viewed as a unilateral programmed interaction; if both players are specified, the game could just as well be an algorithm.

The rule-following of a game is not just the automation of state-revision in response to moves. The important rule-following is in the eyes of the players, since the game constrains them, reducing the behaviors they might gamelessly exhibit. The salient rule-following is in the conformance of the players to the rules for well-formed play. To be sure, a sequence of states S(i) could be identified in unilateral programmed interactions: S(i) = h(O(i)) for some function h. The state constrains the choices of the input I(i'), and one can define the valid keystrokes for a state of edited text:

	I(i') must be in Choices(S(i)) 

as easily as one defines the moves in chess,

	X(i) must be in Choices(S(i)) and 

	Y(i) must be in Choices(T(i)).  

Control systems specify legitimate environmental change and how to respond to change. Games specify the regulation of play and how the board changes with play.

Taking the view that a process is a game requires distinguishing inputs. A social theory (not just an enlarged ontology) is overlaid upon the process so that a distinction between the inputs is inherited from the distinction between individuals. The social validity and significance of the outcome of a game requires building output upon the players' inputs. Players have a joint responsibility for what happens in the game. A stake in the game is traded for a claim to decide the outcome.

Argument, dialectical disputation, is a game. It differs from logic because it is ampliative and defeasible. Outcomes are contingent on play. One is obligated to accept the outcome of a trial or election despite the possibility that had the process continued, or had the process been conducted on a different day, the outcome would have been different. Such nonmonotonicities and indeterminacies do not happen with logics.

Logic could have been about computation, but its founders refused to see the process of calculation as distinct from its form. This is where John Maynard Keynes broke from Alfred North Whitehead, and why Wittgenstein now presides over Russellian ruins. A calculus permits sequential derivation, and a sequence can be a represention of a process. The derivation, S0 |--^i Si amounts to S0 |-- Si, no matter what the i is. In proof theory, the difference between |--^i and |--^j is an accident of axiomatization. In computation, |--^1 should be the definition of a process's progress, and the sequence of Si's should be the computational object itself. Worse, mathematically reductionist thought pervades the mainstream view of logic. |-- is taken to be subservient to |== defined as a mathematical system: semantic entailment serving as the arbiter of syntactic entailment; the equestrian power of string-rewriting put behind the carrying and Currying; derivation systems claimed to be unsound with respect to mathematical models whenever mathematical models are equally incomplete with respect to derivation systems. S is a shorthand for Thm(S), no matter how S yields Thm(S). Worse, still, is the convention in two-valued systems of deduction to find p to be an entailment of S whenever S U {not-p} is inconsistent. Not only is computation thus reduced to transformation, but valid transformation is reduced to valid representation.

In the mathematics of argument, justification is the result of a process. There may not be an ideal process. Assertions are not supposed to be true, but are supposed to be uncontested by both parties to the argument (some assertions may even be legislated by social authority). They are part of the shared basis upon which dispute can occur (with agreement on nothing, there is hardly any reason to inquire about disagreement). They are chess pieces, not parts of the expression of the rules of the game. If there is a process |--^i, then justification is relative to i. The rules of argument constrain the interaction, but the choices of the players co-create the justification. A trial with an undefended defendant hardly inspires confidence in a conviction; a lax inquisitor cannot properly acquit. Chess played as a procedural proxy for a split of a pie does not suffice when the balance of skills does not match the balance of conflicting rights. Critical appraisal of the process refers to appropriateness, efficiency, the entrenchment and consilience of conventions, which might in fact be class inheritance among procedures. These are computational issues. They are issues about interaction, not about representation or transformation. Logic might or might not be computation, but argument must be computation. And it is interactive computation, not algorithmic computation.

Do chess players compute the outcome of their game? Do lawyers and judges not arrive at their conclusions? They do not compute in the sense that the outcome is compelled by the calculus of their courtroom procedure. Having learned that Schroedinger cats are neither dead nor alive until they are observed, surely the theory should inform the linguistic practice, not the reverse. Computation, narrowly construed, seems to imply automation: repeatability of output upon input, causal connectedness, and physical encapsulation of the device. These are unnecessary. (As a separate matter, computation implies discrete data and discrete state transition, but analog computation certainly includes most audio and video signal processing.) Perhaps a probabilistic test of whether a number is prime does not compute its decision, especially if the pseudo-prime numbers are drawn by interacting with the state of the operating system (how in fact probabilism is currently programmed). Perhaps by following the program, one arrives at the decision. Two modems negotiating a speed at which to transmit and receive their signals play a game; in fact, their moves are pre-determined and representable as a function. Still, they do not compute the transmission speed: the nondeterministic interaction with the environment too much compromises even this degree of automation. When an expert system decides which rule of two conflicting rules should govern its behavior, it might conduct a resource-bounded argument with nondeterministic search for arguments. None of these is a computation, narrowly construed. Of course all of these examples are examples of what we would consider computations. Even Turing machines are allowed to consult oracles at times.

Broadly speaking, computation should be whatever results from intentional and teleological rule-following upon symbols. The existence of a program is the test for computation, not the existence of an algorithm. Not just any rule-following is computation, since the objects must be symbolic and the progress goal-directed. Physical systems can be usefully described to be following rules, e.g., following the laws of kinematics. But they can only be computing systems if one thinks there is a rule-maker who has specified nomological rules. Purpose and intention are prerequisites for computation. "Accidental computation" is computation only when one is in the mood for that metaphor. Wittgenstein wonders too, whether one may accidentally calculate or may perform calculation as a social ritual (L. Wittgenstein, Foundations of Mathematics). In any case, it is better to say that the loom weaves the cloth when it computes the pattern, better to have that the congregation is programmed to respond than to say that the biblical reading is algorithmic, better to call it theater only when they are trying to follow the script. If the editor and editing program interactively compute the revised document, then perhaps the game players indeed electively compute the outcome of the game.

I certainly do not care to be mired in the failed culture of analyzing words: computation, computation*, and computation**. It does, however follow from a broadening of computing that most symbolically and socially constructed rule systems are the subject of computational study: monetary and legal systems, elections and languages. It may be that bureaucracy really is a device and that social science has computational foundations.

Processes do not become computations just because they contain computations as subprocesses. The process need not be animated solely by the rule-following, but the process must be informationally connected; the data must persist. Otherwise, my entire day would become a computation just because I did a few minutes of text-editing.

I do not see computation "in the wild" as Brian Smith does (B. Smith, The Origin of Objects), everywhere and every time he undertakes a compositional ontology. To me, computation has to do with the unfolding of prescription, not the unpacking of description. But the first question should really be why there is computation at all -- whether unfolding or unpacking. Why are edicts pronounced piece-by- piece, programs written line-by-line, and both followed step-by-step; why are formulas for logarithms better than tables; why does following the law take time? Why can't there be fascists with instantaneous speeches and instantaneous purges? The answers must have to do with the nature of language and our apprehensions of language and reality, but I prefer to think of going forward in Wittgensteinian thought rather than backward.

There are now clearly four important kinds of formal systems that a philosophy of computation should distinguish: (1) the regulation of well-formedness of representation, (2) the algorithmic implementation of transformation, (3) the programming of interaction, and (4) the regulation of play of a game.

The separation of (2) from (1) is where proof can be split from truth, and consequently is where constructive mathematics begins. Between (1) and (3) is where Herbert Simon hoped to distinguish substantive rationality from procedural rationality. Church and Turing in their day, and Dijkstra recently hoped to reduce (2) to (1), creating the central dogma of computing. Peter Wegner aims to distinguish (2) from (3). The distinction between (1) and (4) occupied Wittgenstein, especially in his Remarks on The Foundations of Mathematics. The reduction of (4) to (1) is where game theory makes its mistake, especially with von Neumann, Oskar Morgenstern, and the equilibria of John Nash. Separating (4) from (1) is where this author has done his work, as have most argumentation theorists such as Stephen Toulmin, expositors of dialectic, such as Nicholas Rescher, and philosophers of legal interpretation, such as H.L.A. Hart.

The study of computation should have more to do with the foundations of applied mathematics (in fact, applied formal systems) than the foundations of mathematics. This is what we are seeing now, in long overdue philosophical discussions of computing. It is good to be able to see formal systems apart from the dogmas of the first formal systems, and a bit sad that it has taken so long to see.