What I missed in Batcher’s Baffler (EWD935a–0)

What I missed in Butcher's Baffler (EWD935a-0)

The remark on p. EWD 935a-3 "I did not fully check it, but ...." is stupid because the check is trivial. It is amazing that I missed that because, one page earlier, I had made the relevant remark, viz. that the OK-relations in $\mathbb{P}2$ -and also those in $\mathbb{P}3$ - are disjoint provided e.i.e.(i+ t). [The remark was too weak to my taste: disjointness of the relations in $\mathbb{P}2$ -and also of those in $\mathbb{P}3$ - is equivalent to (Ei: e.i e.(i+ t)).] And I also remarked that any such predicate would do. If e is such a predicate, so is te . Replacing e.i by te.i would interchange P2 and P3, so "the choice just made is irrelevant". So that is that.

That was stupid, wasn't it? I know what happened. In EWD935 a I tried to present a derivation of Batcher's Baffler, but I did not actually derive it. For I had seen it before, and in that presentation P2 and P3 were not given in terms of e.i but in terms of the very specific choice (i mod 2.t) $< t$ . I introduced e.i more as a short-hand, I am afraid, than as an abstraction.

I discovered my stupidity while lecturing. It was also while lecturing, that I discovered that I could have presented a nondeterministic pro- gram in which at each iteration of the outer repetition -i.e. for each value of t-a fresh predicate e would be chosen.

My mistake is a nice example of the harm done by being overspecific. That Nelly van Gasteren has

EWD940-1

elocuently warned me against being overspecific makes my mistake only worse.

Another moral of the experience is: postpone the reproduction and distribution of EWD's I am going to lecture about until I have actually done so. (I am now going to write EWD941; it is for my course and I shall postpone reproduction until I have given the lecture.)

Austin, 27 September 1985

prof. dr. Edsger W. Dgkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712 - 1188

USA