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.