computational irreducibility
In: 9
I’ll try!
If life is a game who’s instructions you lost, think about science as a way to find out what the rules are by watching people play. You quickly realize that one class of things moves this way or that, and eventually get to enjoy watching more because you can kind of look ahead and see the game strategically.
But then there are pieces that just seem to move the way they move… No other piece moves like them. You can’t project how they’ll move, you can only observe them.
Those pieces are computationally irreducible.
A process or algorithm is “computationally irreducible” if there’s no other, more efficient process you can create to predict what the algorithm will return. For a computationally irreducible algorithm, the most efficient way to see what the it does is to simply run it.
Say you have a computational problem like
1+1+1
You can solve it one step at a time or reduce it into a single step, 1 x 3.
Some problems cannot be reduced.
1+1 is the same number of steps as 1 x 2, so it cannot be reduced further.
Are there any theoretical results for computational irreducibility? Or is it just something Stephen Wolfram wrote about with no theoretical justification?
Latest Answers