Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

1 Answer 1

up vote 1 down vote accepted

For completeness' sake I'll write down what mjqxxxx pointed out, so this question can be marked as answered (if mqjxxxx decides to write his comment as an answer I'll chose his answer as the correct one)

My fallacy was 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.

(thanks mjqxxxx)

share|improve this answer

Your Answer

 
discard

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.