Computable

Robert P. Munafo, 2002 May 7.

Roughly speaking, something (like a number or a set) is "computable" if it can be determined to arbitrary precision using a well-defined repeatable deterministic algorithm in a finite number of steps with a finite amount of information as input. Often such an algorithm and sequence of steps is said to be equivalent to a Turing machine with a given finite input, but that is actually something different. Turing machines, computability, and information theory also seem to be related to the entropy factors in thermodynamics, cosmology and physics.

Problems involving computability share much with the "ruler and compass" problems of Euclidean geometry. There are specific restrictions to the type of input and steps that can be used in the algorithm. For example, you cannot specify an arbitrary irrational number as "input" or as part of your algorithm because the number contains an "infinite" amount of information in its digits — and therefore you can't state the irrational number precisely in your algorithm.

The consequence of this is that, because there are aleph-0 finite algorithms and c real numbers, most real numbers are not computable.

Roger Penrose uses the Mandelbrot Set as an example in a full discussion of this issue in his book *The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics*.

In practice, while actual mathematical objects like the Mandelbrot Set may not be computable in the classical sense, we make do quite well with computable algorithms that generate approximations of the Mandelbrot Set and it can be shown that given enough computing power these approximations are indistinguishable by the naked eye from what the real mathematical object would look like if we could ever actually see one. This is analogous to the fact that if you can draw a circle on paper which looks just as round as a "real" "perfect" circle.