Measuring Program Progress using Information Theory

Computer programs are written to achieve a task. Program testing and verification processes typically ask the question of whether a program achieves its task or not. In this talk I would like to tackle a related but underexamined question, which is whether we can quantify the progress that each program step makes towards achieving its task. This will begin with the idea that each step in a correct program creates some information that is relevant to the task. We will quantify this contribution by using ideas from information theory: compressibility, normalised information distance, and entropy.

This talk will include a discussion of the implications of these ideas for bug finding and program synthesis. I will end the talk by discussing whether such measurement methods could also be useful in analysing programs that represent simulations, for example in computational biology.