  Theory evaluation is a key problem in many areas: machine learning,
scientific discovery, inverse engineering, decision making, software
engineering, design, human sciences, etc. If we have a set of theories that are
able to explain the same set of phenomena, we need a criterion to choose which
one is best. There are, of course, many possible criteria. Model simplicity is
one of the most common criteria in theory evaluation. The Minimum Message
Length (MML) is a solid approach to evaluate theories relative to a given
evidence or data. Theories can be expressed in specific or general
(Turing-complete) languages. First-order logic, and logic programming in
particular, is a Turing-complete language. Evaluating the simplicity of a
theory or program described in a Turing-complete language is much more
difficult than just counting the number of lines or bits. It is, in fact, the
problem of calculating its Kolmogorov complexity, which is uncomputable. Few
works in the literature have been able to present accurate and effective
approximations for a Turing-complete language. In this work, we present the
first general MML coding scheme for logic programs. With this scheme, we can
quantify the bits of information required to code (or send) a theory, a set of
data or the same data given the theory. As a realization of the above-mentioned
schemes, we present a software tool which is able to code and evaluate a set of
alternative (stochastic) theories (programs) against a set of examples. We
illustrate the application of the tool to a variety of non-probabilistic and
probabilistic scenarios.
