Abstract

The logic of scientific discovery is now a concern of computer scientists, as well as philosophers. In the computational approach to inductive inference, theories are treated as algorithms (computer programs), and the goal is to find the simplest algorithm that can generate the given data. Both computer scientists and philosophers want a measure of simplicity, such that simple theories are more likely to be true than complex theories. I attempt to provide such a measure here. I define a measure of simplicity for directed graphs, inspired by Herbert Simon''s work. Many structures, including algorithms, can be naturally modelled by directed graphs. Furthermore, I adapt an argument of Simon''s to show that simple directed graphs are more stable and more resistant to damage than complex directed graphs. Thus we have a reason for pursuing simplicity, other than purely economical reasons.