You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Perplexed comments on Gödel and Bayes: quick question - Less Wrong Discussion

1 Post author: hairyfigment 14 April 2011 06:12AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (36)

You are viewing a single comment's thread. Show more comments above.

Comment author: Perplexed 14 April 2011 03:12:38PM *  1 point [-]

A little more subtle, I think. Recall that the key idea in Godel's proof was 'Godelization" - he exhibited an algorithm which matched each sentence about arithmetic in some formal language with a particular natural number. And he also exhibited an algorithm going in the opposite direction - given any number (or formula representing a number), it would either tell you that the number does not correspond to a sentence, or it would tell you what sentence that number represents.

Now suppose we tried to duplicate this with real numbers. Our language still has only a countable number of sentences, so we still want to map sentences to integers (or naturals). So all we need is an algorithm - given any real number or formula representing a real number, determine whether that number is an integer. But there is no such algorithm. It isn't so much a difficulty in simply encoding or defining the word "integer", it is a difficulty in producing an operational or algorithmic definition of "integer".

Incidentally, returning to the original Godel and arithmetic, the only way Godel was able to produce an algorithm deciding whether a formula representing a number does or does not also represent a sentence ... the only way he could be sure his algorithm terminated, was to assume a standard model of arithmetic. I.e., count backward and you will eventually get to zero in a finite number of steps. That is, Godel's undecidable sentence could be assumed either true or false, given the axiomatization of arithmetic. But, also assuming a standard model, that sentence can only be true.

Comment author: prase 14 April 2011 06:38:40PM *  1 point [-]

So all we need is an algorithm - given any real number or formula representing a real number, determine whether that number is an integer. But there is no such algorithm. It isn't so much a difficulty in simply encoding or defining the word "integer", it is a difficulty in producing an operational or algorithmic definition of "integer".

Yes, this was approximately what I meant by "encoding the word integer". Somehow it didn't occur to me that it may be difficult, or even impossible, to test real numbers for integerness. Still, I am not sure if I understand. A concrete example of a uniquely defined real number whose integerness is unknown would help.

Comment author: Perplexed 15 April 2011 01:16:33AM 1 point [-]

I think you misunderstood. I said there exists no algorithm such that for all formulas it can decide whether the formula represents an integer. Which is equivalent to saying that forall algorithms there exists a formula which can't be decided.

In other words, the way this game is played, first you specify the algorithm and then I supply the formula that breaks it.

Comment author: prase 15 April 2011 09:03:28AM 0 points [-]

I understood that the algorithm valid for all formulae had to be produced in advance, but still I found it strange that it doesn't exist. Further thinking about it it doesn't seem so strange after all.