Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines

Details Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines

2011-02-26

arxiv.org/abs/1102.5389v2

Computer Science

Computational Complexity

Proceedings of the 3rd. International workshop on Physics and Computation 2010 on the Nile, Egypt, pages 175-198, 2010. Forthc

Scientific paper

The aim of this paper is to undertake an experimental investigation of the trade-offs between program-size and time computational 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, 3 and 4 states--denoted by (n,2) with n the number of states--with particular attention to the runtimes and space usages when the machines have access to larger resources (more states). We report that the average runtime of Turing machines computing a function almost surely increases as a function of the number of states, indicating that machines not terminating (almost) 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 a comparison among these classes. For a selection of functions the comparison was extended to (4,2). Our study revealed various structures in the micro-cosmos of small Turing machines. Most notably we observed "phase-transitions" in the halting-probability distribution that we explain. Moreover, it is observed that short initial segments fully define a function computed by a Turing machine.

Affiliated with

Also associated with

No associations

Rating

Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines 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 Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-302226