Access to the full content is only available to members of institutions that have purchased access. If you belong to such an institution, please log in or find out more about how to order.



Computability and information

DOI: 10.4324/9780415249126-Y008-1
Version: v1,  Published online: 1998
Retrieved March 26, 2019, from

Article Summary

The standard definition of randomness as considered in probability theory and used, for example, in quantum mechanics, allows one to speak of a process (such as tossing a coin, or measuring the diagonal polarization of a horizontally polarized photon) as being random. It does not allow one to call a particular outcome (or string of outcomes, or sequence of outcomes) ‘random’, except in an intuitive, heuristic sense. Information-theoretic complexity makes this possible. An algorithmically random string is one which cannot be produced by a description significantly shorter than itself; an algorithmically random sequence is one whose initial finite segments are almost random strings.

Gödel’s incompleteness theorem states that every axiomatizable theory which is sufficiently rich and sound is incomplete. Chaitin’s information-theoretic version of Gödel’s theorem goes a step further, revealing the reason for incompleteness: a set of axioms of complexity N cannot yield a theorem that asserts that a specific object is of complexity substantially greater than N. This suggests that incompleteness is not only natural, but pervasive; it can no longer be ignored by everyday mathematics. It also provides a theoretical support for a quasi-empirical and pragmatic attitude to the foundations of mathematics.

Information-theoretic complexity is also relevant to physics and biology. For physics it is convenient to reformulate it as the size of the shortest message specifying a microstate, uniquely up to the assumed resolution. In this way we get a rigorous, entropy-like measure of disorder of an individual, microscopic, definite state of a physical system. The regulatory genes of a developing embryo can be ultimately conceived as a program for constructing an organism. The information contained by this biochemical computer program can be measured by information-theoretic complexity.

Citing this article:
Calude, Cristian S.. Computability and information, 1998, doi:10.4324/9780415249126-Y008-1. Routledge Encyclopedia of Philosophy, Taylor and Francis,
Copyright © 1998-2019 Routledge.

Related Searches