Filosofı́a de la Ciencia, Universidad de Sevilla§

The aim of this paper is to undertake an experimental investi-gation of the trade-offs between program-size and time compu-tational complexity. The investigation includes an exhaustive exploration and systematic study of the functions computed by the set of all 2-color Turing machines with 2 states –we will write (2,2) – and 3 states –we write (3,2) – with particular atten-tion to the runtimes, space-usages and patterns corresponding to the computed functions when the machines have access to larger resources (more states). We report that the average runtime of Turing machines comput-ing a function increases –with a probability close to one – with the number of states, indicating that machines not terminating (al-most) immediately tend to occupy all the resources at hand. We calculated all time complexity classes to which the algorithms computing the functions found in both (2,2) and (3,2) belong to, and made comparison among these classes. For a selection of functions the comparison is extended to (4,2). Our study revealed various structures in the micro-cosmos o