Unpredictability and Computational Irreducibility

Details Unpredictability and Computational Irreducibility Unpredictability and Computational Irreducibility

2011-11-17

arxiv.org/abs/1111.4121v2

Computer Science

Computational Complexity

20 pages, 5 figures

Scientific paper

We explore several concepts for analyzing the intuitive notion of computational irreducibility and we propose a robust formal definition, first in the field of cellular automata and then in the general field of any computable function f from N to N. We prove that, through a robust definition of what means "to be unable to compute the nth step without having to follow the same path than simulating the automaton or the function", this implies genuinely, as intuitively expected, that if the behavior of an object is computationally irreducible, no computation of its nth state can be faster than the simulation itself.

Affiliated with

Also associated with

No associations

Rating

Unpredictability and Computational Irreducibility 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 Unpredictability and Computational Irreducibility, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unpredictability and Computational Irreducibility will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350046