Complexity of a number

This article page is a stub, please help by expanding it.

A variant of Kolmogorov complexity is defined as

The complexity of a number $\scriptstyle n\,$ is the smallest number of states needed for a BB-class Turing machine that halts with a single block of $\scriptstyle n\,$ consecutive 1s on an initially blank tape.

The corresponding variant of Chaitin's incompleteness theorem states

In the context of a given axiomatic system for the natural numbers, there exists a number $\scriptstyle k\,$ such that no specific number can be proved to have complexity greater than $\scriptstyle k\,$, and hence that no specific upper bound can be proved for $\scriptstyle \Sigma (k)\,$ (Cf. Rado's sigma function Sigma(n).)

The latter is because "the complexity of $\scriptstyle n\,$ is greater than $\scriptstyle k\,$" would be proved if "$\scriptstyle n\,>\,\Sigma (k)\,$" were proved.

As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least value $\scriptstyle k\,$ for which this is true is far less than 10↑↑10 (using Knuth's up-arrow notation); consequently, in the context of ordinary mathematics, neither the value nor any upper-bound of Σ(10↑↑10) can be proved. (Gödel's first incompleteness theorem is illustrated by this result: in an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form "Σ(10↑↑10) = $\scriptstyle n\,$", and there are infinitely many true-but-unprovable sentences of the form "Σ(10↑↑10) < $\scriptstyle n\,$".)