Applications, I/O's and Side-Effects

(Originally published on: Wed 11 of Aug, 2004)
Scott sent me an incredibly timely reference: "Computation Beyond Turing Machines" by Peter Wegner and Dina Goldin, April 2003/Vol. 46, No. 4 COMMUNICATIONS OF THE ACM.

The gist of their thesis is: "In each case, interaction between the program and the
world (environment) that takes place during computation plays a key role that cannot be replaced by any set of inputs determined prior to the computation."

This directly connects with thinking I was doing this morning on side-effects and models of computation. What originally started my train of thought was the observation that while functional models of computation are commonplace, they are seldom used to model entire applications. Usually, they model a single function and its data-in/data-out transformation.

However there is no reason why functional models can't be applied to represent the behavior of an entire application. Doing so brings up two interesting things to consider.

First is the state-space of the inputs. The state-space for a relatively trivial application (like a word processor) can be nearly infinite. This makes it much more difficult to quantitatively state the range of the application in terms of operations on its domain.

Second is the fact that most applications have changing inputs during the course of execution, which is at odds with the standard functional model of outputs as a function of initial conditions.

Tackling the first problem can be done using fuzzy computation and isomorphisms. It is possible to reduce the statespace of the inputs by considering only the inputs relevent to the computation to be performed rather than all possible values.

Second, my observations from this morning illustrate a model for beginning to map interaction into a functional model....

TBD...