The Indeterminacy of Computation

We describe indeterminacy and explain its impact on current thinking about the nature of computation.

This Element describes computational indeterminacy which occurs when a fixed physical system potentially computes different functions. The phenomenon has potential significance in neuroscience and cognitive science, artificial intelligence, the theory of algorithms, and circuit design. This title is also available as Open Access on Cambridge Core.This element describes an emerging and intriguing topic: computational indeterminacy. Indeterminacy occurs when a fixed physical system potentially computes several different functions, and there is no fact of the matter which of these is actually being computed by the system. The phenomenon of computational indeterminacy has potential significance for a number of fields, including neuroscience and cognitive science, artificial intelligence (AI), the theory of algorithms, and circuit design. Here we address foundational and philosophical issues. We also explain how the indeterminacy phenomenon impacts on current thinking about the nature of physical computation. Computational indeterminacy is the subject of a growing number of articles in specialist journals, and The Indeterminacy of Computation introduces the topic to a wider audience. The style is clear and informal, with many helpful diagrams. This title is also available as Open Access on Cambridge Core.