`the smallest natural number that cannot be described by an English sentence of up to one thousand letters`

Such a number cannot exist – if we take the sentence above as a legitimate description of the number – as the sentence above both describes the number that cannot be described in less than one thousand letters and yet takes quite a lot less than one thousand letters to do it.

Stolen from P, NP, and NP-Completeness: The Basics of Computational Complexity – which is a less than easy read (for me at least).

###### Related articles

- Root 2 and Proof by Contradiction (casualcalculations.wordpress.com)
- The Visual Argument (eyewonderbooks.wordpress.com)

Advertisements