In article <391AC666.22F32466@ipb.uni-bonn.de>, Boudewijn Moonen <Boudewijn.Moonen@ipb.uni-bonn.de> writes:
> In their seminal - yet, strangely, apparently not widely known - > 1966 paper , 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 , 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  and found it cryptic and > obscure, > > [...] > > I therefore have the following questions: > > 1) What is the actual status of the Bohm-Jacopini 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 GOTO-less 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