Complejidad descriptiva y computacional en máquinas de Turing pequeñas

International audienceWe start by an introduction to the basic concepts of computability theory and the introduction of the concept of Turing machine and computation universality. Then se turn to the exploration of trade-offs between different measures of complexity, particularly algorithmic (program-size) and computational (time) complexity as a mean to explain these measure in a novel manner. The investigation proceeds by an exhaustive exploration and systematic study of the functions computed by a large set of small Turing machines with 2 and 3 states with particular attention to 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 computing a function increases as a function of the number of states, indicating that non-trivial machines tend to occupy all the resources at hand. General slow-down was witnessed and some incidental cases of (linear) speed-up were found. Throughout our study various interesting structures were encountered. We unveil a study of structures in the micro-cosmos of small Turing machines.En este trabajo ofrecemos algunos de los resultados obtenidos al estudiar las funciones calculadas por máquinas de Turing con un alfabeto de dos símbolos y un número de estados entre 1 y 3. Presentamos detenidamente el modelo de máquina de Turing empleado, donde la cinta es ilimitada en un solo sentido, y no existe estado de parada. Mostramos gráficamente cómo es posible representar la función calculada por una máquina, así como las computaciones realizadas para ello. Vemos que al aumentar el número de estados, si bien es posible que algunas funciones se calculen con mayor rapidez, por lo general aumenta considerablemente el tiempo medio de computación