Computational irreducibility

Computational irreducibility is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science. Computations that cannot be sped up by means of any shortcut are called computationally irreducible. Stephen Wolfram proposed the principle of computational irreducibility, which says that the only way to determine the answer to a computationally irreducible question is to perform, or simulate, the computation. An irreducible computation is a bit like a story that resists summarization at any level of detail.

Links

• Wikipedia entry for Computational irreducibility
• MathWorld entry for Computational irreducibility