Abstract

Fundamentally, Computer Science is hard because the world is not known to be deterministic. Clearly, if the opposite were true, computation could be done in advance since the right computation to carry out would be known, and all software could be reduced to a hard-coded result.

In any realistic problem setting, the lack of premature knowledge about variable outcomes is the fundamental reason that they are problems at all. This is essentially what entropy is about—it is a measure of the lack of predictability of a problem space.

This talk explores the background for the discussion of entropy in Computer Science, and how it relates to other uses of the term ‘entropy’, as well as giving a formal foundation of reasoning about entropy. Finally, I show how entropy directly influences real-world challenges by examining Shannon’s source coding theorem as well as its proof.