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?


Read this:


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.

  • 4
    You forgot the third option, where it returns FILE_NOT_FOUND ;) – FrustratedWithFormsDesigner Jun 3 '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 3 '11 at 19:59
  • Are you talking about cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD658.html? – S.Lott Jun 3 '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 3 '11 at 20:24
  • Probably not 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 3 '11 at 20:42

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.)

  • Thank you! Yes, it's definitely a paper by Dijkstra that I'm referring to. – Dijkstra Reader Jun 4 '11 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.