Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Topic: Status of Bohm-Jacopini Theorem
Replies: 5   Last Post: May 12, 2000 1:51 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Robert Hill

Posts: 529
Registered: 12/8/04
Re: Status of Bohm-Jacopini Theorem
Posted: May 11, 2000 1:34 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 [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 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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2016. All Rights Reserved.