64

In Dijkstra's paper "Humble Programmer", he mentions that he gave some volunteers a problem to solve:

“I have run a little programming experiment with really experienced volunteers, but something quite unintended and quite unexpected turned up. None of my volunteers found the obvious and most elegant solution. Upon closer analysis this turned out to have a common source: their notion of repetition was so tightly connected to the idea of an associated controlled variable to be stepped up, that they were mentally blocked from seeing the obvious. Their solutions were less efficient, needlessly hard to understand, and it took them a very long time to find them.”

What was the problem Dijkstra gave to the volunteers? What were the solutions?

splattne
  • 103
  • 5
user712092
  • 1,412
  • 3
    I'd bet on something recursive. EWD654 "In honor of Fibonacci" seems to be a good candidate – gnat Oct 11 '11 at 21:04
  • This question could be fine as long as people don't use this as an opportunity to guess or speculate: it may be difficult to find out, but it has an answer and historical questions are on-topic here. –  Oct 14 '11 at 19:12
  • 9
    That quote came from EWD340 "Very Humble Programmers". I wasn't able to find an exact description of what the experiment was, but here is a link to the transcript of his full talk. http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html – Tyler Ferraro Oct 15 '11 at 02:43
  • 2
    Can anyone find a Dijkstra quote which is complimentary about anything? My favorite quote about him is "arrogance in computer science is measured in nano-Dijkstras" -- Alan Kay – James Anderson Oct 25 '11 at 06:21
  • We must be very careful when we give advice to younger people: sometimes they follow it! ... heh :-) source : http://en.wikiquote.org/wiki/Edsger_W._Dijkstra – Robert French Oct 26 '11 at 23:03

1 Answers1

10

The "Dining philosophers problem" was the problem presented.

Basically there are 5 philosophers that need to eat. (imagine a plate of never ending food in front of each philosopher), between each plate is a fork (5 plates, 5 forks, 5 philosophers).

A philosopher can only eat if he is holding both the fork to the right and the fork to the left. (only two philosophers can eat at any given time).

A fork may be picked up anytime it is available and put down if it is being held. Each fork must be picked up interdependently. (one at a time).

While a philosopher is not eating, they are thinking (the need to alternate states is what drives the problem).

How do you allow each of them to eat and alternate thinking (so the others can eat) without creating a deadlocked system (where one philosopher is holding one fork and waiting for the other, preventing another philosopher from eating).

This has its roots in concurrent systems and is a typical university question presented when discussing Concurrency.

I believe that 4 or 5 "official" algorithms have been developed to solve the problem but a quick search on google for "Dining philosophers problem" will get you a vareity of results.

If you read the original version of the paper in the footnotes on page 866 it states: "Proceedings of the IFIP Congress 1965, 213-217. " Solutions of a problem in concurrent programming control."

The problem in concurrency and shared resources is the "Dining Philosophers Problem". :-)

Hope that helps.

Spoike
  • 14,773
Robert French
  • 421
  • 6
    Since this is mainly a historical question, any sources? – yannis Oct 26 '11 at 21:48
  • 1
    Actually no, the sources you provide don't seem to reference the Dining philosophers problem as the one Dijkstra gave to the volunteers. Am I missing something? What I'm looking for is credible sources to support your The "Dining philosophers problem" was the problem presented claim, not descriptions of the problem itself (although your links are highly informative and interesting). – yannis Oct 26 '11 at 23:10
  • @Robert Thanks for the links. :) (don't remove them, they might be useful to others) I am looking forward whether it was the problem he gave. – user712092 Oct 26 '11 at 23:18
  • ahhh I misunderstood the sources, you're attempting to determine if it was Dijkstra that poised the question in the first place ... Everything I have ever read on this problem lists him as the source. I didn't know it was up for debate. – Robert French Oct 26 '11 at 23:31
  • 4
    @RobertFrench What we are looking for is what was the specific problem Dijkstra mentions in the quote in the question, and sources that prove it, not just any problem Dijkstra formulated. There is nothing in the quote that even suggests it was one of his own problems, it could be any problem really. Of course the Dining philosophers is one of Dijkstra's originals (with some help from CAR Hoare), noone is debating that, but that has nothing to do with the question. – yannis Oct 26 '11 at 23:48
  • @YannisRizos
    got it ;-) My answer stands. If you read the original version of the paper ( www.jdl.ac.cn/turing/pdf/p859-dijkstra.pdf ) in the footnotes on page 866 it states: "Proceedings of the IFIP Congress 1965, 213-217. " Solutions of a problem in concurrent programming control." Which is the "Dining Philosophers Problem".     – Robert French Oct 27 '11 at 00:10
  • @RobertFrench The footnote references something different entirely. Check at top of page 859, all footnotes are on the Turing Award Citation not on the Humble Programmer itself, and they all refer to Dijkstra's previous papers. Nothing to do with the problem in the quote. – yannis Oct 27 '11 at 00:31
  • Google "problem in concurrent programming" ;) – Robert French Oct 27 '11 at 02:05
  • 4
    This is just plain wrong. "Solutions of a problem in concurrent programming control" is the Dining Philosophers Problem, and it is referenced in the Humble Programmer as one of Dijkstra's earlier works in the citation, but claiming that it's also the problem in the quote is unverifiable. – yannis Oct 27 '11 at 14:58
  • @RobertFrench Hey Robert, since our discussion is getting a little bit long for comments and we don't seem to find common ground, I've asked others on chat to take a look at it. Anyways, thank you for reminding me of the Dining Philosophers... – yannis Oct 27 '11 at 15:58
  • let us continue this discussion in chat – Robert French Oct 27 '11 at 17:41
  • 1
    This doesn't appear to have anything to do with repetition. I don't think it's the true historical answer. – Wildcard Nov 30 '15 at 09:10