Feedback on Wegner Paper

Hypotheses: Wegner advances several hypotheses in his paper and you
did a good job of identifying them. However, there is one main one, to
which all the others are subsidiary, so I will focus on that, which
is:

	That interactive machines are strictly more powerful than
	algorithms, and constitute a paradigm shift for computer
	science.

Evidence: Wegner advances a host of arguments to support this
hypotheses. Unfortunately, they are all faulty in one respect or
another. Some of you were too uncritical in accepting his arguments at
face value. On the other hand, I think there is a Good Idea here,
which deserves to be drawn out. It's just a shame that Wegner makes
such a hash of doing so. So, I reserved full credit to those whose
criticism was constructive in trying to see what could be rescued from
this idea. Below, I give some examples of the problems with Wegner's
arguments.

1. Since the first half of the hypothesis above is essentially
   theoretical in nature, one would expect to see a formal definition
   of both interactive machines and algorithms, then a proof that the
   first was a strict superset of the second. For algorithms, he
   appealed to the standard definition of Turing Machines. However,
   there was neither a formal definition of interactive system, nor a
   proof of the superset relation.

2. Wegner's informal argument depends on Turing Machines not being
   able to take input from the environment during processing. I think
   a lot of theoreticians would dispute this exclusion. A great deal
   of work has been expended in formally defining input/output
   functions, for instance. There has also been formal work on
   potentially infinite data-structures, such as lazy lists, in which
   the end of the list contains a function for generating further
   elements on an "as needed" basis. This final function could indeed
   take input from the environment. So theoreticians have certainly
   not acted as if they accept this diminished definition of an
   algorithm. I was not expecting you to know this theoretical
   background, although you might have questioned this critical
   assumption in Wegner's argument.

3. Wegner draws a strict distinction between concurrency and
   interaction (top p5). However, by his own account these two forms
   of computation differ only in a modelling decision. Consider two
   interacting agents. If one wants to model both, then this is
   concurrency and has an algorithmic model. However, if you treat one
   agent as in the model and the other as part of the environment,
   then this becomes an interaction machine. 

4. The discussion at the bottom of p5, where he allows that a closed
   algorithmic system can have an open, non-algorithmic subsystem,
   seems to completely undermine his hypothesis. Consider, for
   instance, enclosing an interactive system within an algorithmic
   identity function. This would enable the set of algorithms to
   contain the set of interactive systems as a strict subset --- the
   opposite of his hypothesis.

5. On p10 Wegner claims that the theory of interaction machines is
   incomplete. Firstly, this is yet another formal claim for which he
   provides no proof, despite claiming that there is a proof that does
   not require diagonalisation. Secondly, this claim does not help
   him, since the theory of algorithms is also incomplete. Indeed,
   Peano Arithmetic can be viewed as the theory of algorithms on the
   natural numbers, so Goedel's Incompleteness Theorem shows this
   algorithmic theory already to be incomplete.

6. On p3 Wegner claims that interaction machines cannot be completely
   described by first-order logic. If interaction machines are defined
   as concurrency in which one or more of the agents are excluded from
   the model (see pt 3 above), then this claim is true by
   construction, but rather vacuous.  It then seems unfair to totally
   ignore the many logical models of concurrency, such as Milner's
   Calculus of Communicating Systems, which was a fairly mature at the
   time of Wegner's paper.

I could go on in this vein, but that's probably enough for now. 

  On the other hand, it is clearly interesting to think about
computational systems that can only be partially modelled and about
which we can only have partial understanding, due to their interaction
with the environment. It is also interesting to think about machines
that are not intended to terminate, e.g. operating systems, web
browsers. A lot of theoretical computer science has investigated
precisely such situations, so Wegner's wholesale rejection of logic
and formal methods seems uninformed.