Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

how much information is required to construct the equation: $$ X^2 - 2=0 \; ? $$ suppose, in a spirit of seasonal festivity, we squander a few further bits, and pamper ourselves with the additional condition: $$ x \gt 1 $$ we know that a solution to this equation is specified by $$ x=\sqrt{2} $$ expressed in this way, it might be argued that the solution contains a quantity of information, $I$, which has the same order of magnitude as the information content of the question.

on the other hand it is evident that, measured by the activities of a suitably co-operative Turing machine, the quantity of information in the solution is in fact (something like): $$ ln \; \aleph_1 $$ how should i attempt to reconcile these two points of view?

share|cite|improve this question

In the sense of Kolmorogrov complexity the information content of $\sqrt 2$ is the length of the shortest program to calculate it. The exact value depends on your language, but it is not huge. It is certainly not infinite.

share|cite|improve this answer
thank you, Ross. that is a useful new concept for me, though i have envisaged something similar. however, a new question emerges naturally from this answer: what information is required for the interpretation and implementation of the algorithmic procedure itself, which might be regarded as considerably greater that the Kolmogorov Complexity of a particular procedure? or is this properly viewed as a shared burden which is not the responsibility of any particular computable irrational, and hence making only a negliglible contribution to the info content of particular numbers? – David Holden Dec 17 '13 at 18:03
If your model is a Turing machine, for example, we count the number of states. The "operating system" that interprets the list of states and keeps track of where you are on the tape is usually not counted. – Ross Millikan Dec 17 '13 at 18:23
thx again. provokes this question (slightly off-topic, but grateful to glean a little knowledge), is there is a concept of a machine which can gradually elaborate its state-space, transition-matrix and output/movement functions, and internalize a hypothesis-testing algorithm - i.e. a Turing-machine with the potential for evolution? obviously this would still be a Turing machine. but if it had one probabilistic input to its "problem-selection" subalgorithm - determining its learning trajectory - how would one describe the family of such machines as a function of computation time? – David Holden Dec 17 '13 at 18:38
There may be. I am not up on that area. – Ross Millikan Dec 17 '13 at 18:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.