# One cannot know if a number could be written any shorter according to Gödel's incompleteness theorem

I am reading Tor Nørretranders (cannot find the English version, sry) and he states that Gödel's incompleteness theorem implies that we cannot know if we can write a number any shorter (e.g. $0.3333333$... as $\frac{1}{3}$) until we find the shorter version. Until now there's no lack of clarity, but the following keeps boggling my mind: It is not possible to show that there is no shorter version to write a number.

I am having a real struggle with this statement because assumed I have got a certain number $x$ which has $y$ digits, then $y$ is a finite number. This implies I can loop through all possible statements (of course only in theory) that can be written in less than $y$ characters/digits/whatever and check if any of these instructions/algorithms outputs $x$. If there is no such algorithm within this set of algorithms which can be written using less than $y$ characters, then the number cannot be written any shorter which would be a contradiction to Gödel or at least Tor Nørretranders.

However I seriously doubt I could think of something these two geniuses couldn't.

(My approach was that I could invent an infinite number of new notations to use, such as a "new logarithm" or whatever, but somehow I just cannot think it through to the end)

PS: Sorry, couldn't think of a more appropriate title.

-
I think that's actually Chaitin's result, not Godel. – user58512 Feb 17 '13 at 21:30
Maybe, I don't know, however Tor Nørretranders clearly states (translated by me) "However, it is not possible to say, that it [the number] could be written any shorter. This is Gödel's discovery." – Peter Feb 17 '13 at 21:37
What you're missing is that you can't, in general, check if a particular algorithm outputs $x$. You can run the algorithm, and if it outputs a wrong digit at some point, or halts early, then you know it doesn't output $x$. But since you can't tell if an algorithm will ever halt, you also can't tell if an algorithm won't eventually start outputting more digits of $x$. – mjqxxxx Feb 17 '13 at 21:42
Oh that makes perfectly sense! He wrote that some pages before, I guess I should've thought of that myself -.- If you would post this as an answer I could mark it as answering-my-question ;) – Peter Feb 17 '13 at 21:47