11

Salutations. Dijkstra wrote that even a few lines of seemingly simple code could be hopelessly ambiguous. In at least one work, which I can't find now to save my life, he gave a little example program to demonstrate this ambiguity. Can anybody point me to a paper of his where he includes one of these examples?

Dijkstra Reader
  • 111
  • 3

2 Answers2

11

Read this:

http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions

http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ has nice coverage; search for "halting problem"

There are several forms of the essential halting contradiction.

def halts( code_block ):
    # Some magical code

def whistler():
    while halts(whistler): 
        sys.whistle( 1 )

Does the "whistler" whistle zero, once or an infinite number of times?

If the halts() function determines that the function whistler appears to halt, the function whistler can't halt.

If the halts() function determines that the function whistler does not appear halt, the function whistler halts.

Therefore, the halts() function can't exist.

S.Lott
  • 45,264
  • 6
  • 90
  • 154
  • 4
    You forgot the third option, where it returns `FILE_NOT_FOUND` ;) – FrustratedWithFormsDesigner Jun 03 '11 at 18:47
  • 2
    Thanks! What Dijkstra was describing in the paper I read wasn't the halting problem, though. It's just a few lines of simple code, but you can't tell what it means. The context is that Dijkstra is talking about methods he uses to demonstrate to audiences that programming is hard, therefore programmers must be humble. Note that the paper is not, I am sad to say, "The Humble Programmer." :) – Dijkstra Reader Jun 03 '11 at 19:59
  • Are you talking about http://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD658.html? – S.Lott Jun 03 '11 at 20:00
  • Thanks again. Sad to say, that's not the one. In the paper that I'm referring to, Dijkstra specifically says programming is hard, even for clever people, we have to respect that, "For example, what does the following little program do?" – Dijkstra Reader Jun 03 '11 at 20:24
  • Probably not http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html. But I lift it up as a common citation on how hard programming is. – S.Lott Jun 03 '11 at 20:42
  • Totally. Indeed, not that one either. It's driving me crazy that I can't find it. I think the paper is one of his overview ones, like "The Humble Programmer." – Dijkstra Reader Jun 03 '11 at 20:49
  • WED340 is "The Humble Programmer." – S.Lott Jun 03 '11 at 20:50
  • Right on. I meant: the paper I'm talking about is not "The Humble Programmer," but it is an overview. – Dijkstra Reader Jun 03 '11 at 22:19
  • @S.Lott: Rewrote those bits a bit to make them more understandable (I hope). Please revert if you think they're bad. – Billy ONeal Jun 04 '11 at 00:04
1

Are you sure that the paper was by Dijkstra? Reflections on Trusting Trust by Ken Thompson sounds like it could be what you were thinking of. It demonstrates how absolutely simple, straightforward, and correct programs could wind up doing something absolutely unexpected that isn't visible at all in the source. Even if it isn't what you were thinking of, it is a worthwhile paper to read.

Going a different direction, if you want excellent examples of short programs with surprising behavior, the underhanded C contest is great. For example look at the 2008 winner. The challenge was to write a command line program to blank out part of a picture, in such a way that the picture visually was blanked out perfectly, but the file retains some information about the redacted part of the image. AND in such a way that your code could pass code review. (You could choose the format that the picture is stored in.)

btilly
  • 18,250
  • 1
  • 49
  • 75