Computer Science – Computational Complexity
Scientific paper
2011-04-18
Computer Science
Computational Complexity
18 pages, 4 figures
Scientific paper
There are several forms of irreducibility in computing systems, ranging from undecidability to intractability to nonlinearity. This paper is an exploration of the conceptual issues that have arisen in the course of investigating speed-up and slowdown phenomena in small Turing machines. We present the results of a test that may spur experimental approaches to the notion of computational irreducibility. The test involves a systematic attempt to outrun the computation of a large number of small Turing machines (all 3 and 4 state, 2 symbol) by means of integer sequence prediction using a specialized function finder program. This massive experiment prompts an investigation into rates of convergence of decision procedures and the decidability of sets in addition to a discussion of the (un)predictability of deterministic computing systems in practice. We think this investigation constitutes a novel approach to the discussion of an epistemological question in the context of a computer simulation, and thus represents an interesting exploration at the boundary between philosophical concerns and computational experiments.
Joosten Joost J.
Soler-Toscano Fernando
Zenil Hector
No associations
LandOfFree
Empirical Encounters with Computational Irreducibility and Unpredictability 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 Empirical Encounters with Computational Irreducibility and Unpredictability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Empirical Encounters with Computational Irreducibility and Unpredictability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-71689