brainwagon

It’s actually not just hard in the sense that you normally think of as hard. You might think that if you worked hard, you could figure out what programs actually do. Ed Felton shows that this simply isn’t true. In his simple Python scripts, he asks a question: “is there any combination of inputs to make the program print the word ‘Drat’?” Here’s the program:

import sys, sha
h = sha.new(sha.new(sys.argv[1]).digest()[:9]).digest()

if h.startswith("abcdefghij"):
    print "Drat"

It usually surprises people who don’t have computer science degrees that there is no practical way to tell. Alan Turing formalized this idea: it’s basically impossible to provide an algorithm to determine any non-trivial property of programs (such as whether they halt). Any legislation which requires somebody to evaluate the complete behavior of any program is not just absurd and impractical, but simply not possible.

I addressed the same question in a similar way in a previous post.

Addendum: The statement above is actually subtly incorrect (I should have referred back to my old theory of computation textbooks). I was trying for a description of Rice’s theorem. The idea here is that there is no algorithm (equivalently, you can’t build a Turing machine) to decide with generality whether another Turing machine (for example) accepts a particular string. Or halts. Or halts on an empty tape. Or, in fact any non trivial property.

From Wikipedia:

Using Rogers’ characterization of acceptable programming systems, this result may essentially be generalized to most computer programming languages: there exists no automatic method that decides with generality non-trivial questions on the black-box behavior of computer programs. This is one explanation of the difficulty of debugging.