Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Status of BohmJacopini Theorem
Posted:
May 11, 2000 1:34 PM


In article <391AC666.22F32466@ipb.unibonn.de>, Boudewijn Moonen <Boudewijn.Moonen@ipb.unibonn.de> writes:
> In their seminal  yet, strangely, apparently not widely known  > 1966 paper [1], Bohm and Jacopini established the fundamental > result that any computer program can be rewritten as a *structured* > program, i.e. a program using recursively only the following three > basic flow control constructs > >  sequence >  iteration >  alternative > > (as a side remark, they even show the first two suffice). Together > with Dijkstra's notorious letter to the editor [2], where this result > is cited, this got structured ("GOTOless") programming off the ground. > > However, there seem to be some reservations around about how rigorously > this has been proved. > > [...] > > Thus I decided to look up the old paper [1] and found it cryptic and > obscure, > > [...] > > I therefore have the following questions: > > 1) What is the actual status of the BohmJacopini result nowadays? > Is it considered as having been proved rigorously, or only > sketched, or is its proof regarded as being incomplete? > > 2) Is there an elaborated version of their result somewhere in > the accessible literature? > > 3) Can someone give an intuitive/heuristic argument why their result > holds? > > Any comment welcome.
D.E. Knuth's famous paper "Structured Programming with GOTO statements" (which was probably in Comm. ACM in 1974) cites a paper (or letter or note) by D.C. Cooper, which points out that Boehm and Jacopini's paper says less than it seems to say. I think (that Knuth says that Cooper says) that B&J's paper effectively says not much more than this: given a program P in a language L, we can write a GOTOless interpreter I for language L. We can then execute I with P as input.
Disclaimers: I have never read the B&J paper, or Cooper's paper (despite the fact that Cooper was later my boss from 1975 to 1977). Though I have read the Knuth paper more than once, I have not read it for at least 15 years. So my memories may be all wrong.
 Robert Hill Information Systems Services University of Leeds



