Complejidad descriptiva y computacional en maquinas de Turing pequenas

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-508789

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.