Computer Science – Computational Complexity
Scientific paper
2010-10-07
Computer Science
Computational Complexity
Art\'iculo en espa\~nol. Actas de las V Jornadas Ib\'ericas, L\'ogica Universal e Unidade da Ciencia, CFCUL, 2010. 20 pages, 2
Scientific paper
We 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.
Joosten Joost J.
Soler-Toscano Fernando
Zenil Hector
No associations
LandOfFree
Complejidad descriptiva y computacional en maquinas de Turing pequenas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complejidad descriptiva y computacional en maquinas de Turing pequenas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complejidad descriptiva y computacional en maquinas de Turing pequenas will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-508789