Interesting Consequences of Undecidability

In the book Introduction to Automata Theory — Languages and Computation. The following paragraph is interesting:

What this means is that if we were given a source code of a program, we would be unable to decide what the program does. Only lexical or syntactical properties of the program may be decided. This is interesting because it’s really counter-intuitive! You’d think that given the source code and read through it we can systemically figure out what it does. Not true. This means is that another program, B, cannot figure out what program A does.

Interestingly enough, this implies that no anti-virus will ever be totally effective, or any other types code detection software, because it is undecidable what a program does. There will always exist programs which can’t be detected. I knew this when I was young, from the fact that AV programs always update their virus databases, so naturally that meant there was no systemic way to detect mischievous programs. I wondered if the updates would ever stop in the future. Now I know this will never happen because of this consequence of undecidability.

Leave a Reply

Your email address will not be published. Required fields are marked *