- #1
- 4,119
- 1,718
This question is about two different ways of Godel numbering - assigning natural numbers to well-formed formulas in a formal language.
Godel uses an ingenious and complicated mapping involving Cantor's pairing function (which is a bijection between N and N x N) and the Chinese Remainder Theorem.
Douglas Hofstadter, in his book Godel Escher Bach, uses a much simpler mapping that is really just a transliteration. To every symbol in the formal language, he assignes a three digit code. Then the Godel number of a formula is just the number whose decimal representation is the string of numerals you get when you replace every symbol in the logical formula by its corresponding three digit code.
Hofstadter's map is much easier to understand, and trivial to implement - the Godel number for a formula can be written down in seconds. This contrasts with Godel's map, for which it took my brand new laptop 30 minutes to calculate the Godel number for the formula '0=0' (it's7,286,659, if we map the language symbols '0' and '=' to 0 and 1 respectively, in case anybody's interested).
Godel's map produces much smaller numbers, but that gives no practical advantage, as the numbers still become enormous very very quickly, and are usually impractical to calculate anyway.
Neither map is a surjection onto the natural numbers. Both are primitive recursive.
Both can be simply and naturally extended to map proofs to natural numbers.
So I wonder why Godel chose such a complex approach, rather than Hofstadter's simple and (to me) obvious one. This is made more intriguing by the fact that, in discussions of Godel's proof, I have seen the map he defined described as one of the most brilliant insights in it.
The only practical advantage of Godel's map over Hofstadter's that I can think of is that Godel's copes quite naturally with a language that has an infinite alphabet, which for instance allows for an unlimited number of different one-character symbols for variables, functions and predicates. Hofstadter's approach requires a finite alphabet - in fact his use of three-digit codes places a limit of 1,000 on the number of different characters that can be used.
However, I think the limitation of Hofstadter's map is easily overcome by using the prime character as many times as necessary, so that:
x, x', x'', x''', ... are names of different variables
f, f', f'', f''', ... are names of different functions
p, p', p'', p''', ... are names of different predicates
If that is correct then I am left perplexed as to why Godel chose such a complicated and confusing map. I am very impressed by his map. It would take a brilliantly creative mind to have thought of it. But I just can't see why he didn't take the simple route. Is there some flaw in or limitation of Hostadter's approach that I am missing?
Godel uses an ingenious and complicated mapping involving Cantor's pairing function (which is a bijection between N and N x N) and the Chinese Remainder Theorem.
Douglas Hofstadter, in his book Godel Escher Bach, uses a much simpler mapping that is really just a transliteration. To every symbol in the formal language, he assignes a three digit code. Then the Godel number of a formula is just the number whose decimal representation is the string of numerals you get when you replace every symbol in the logical formula by its corresponding three digit code.
Hofstadter's map is much easier to understand, and trivial to implement - the Godel number for a formula can be written down in seconds. This contrasts with Godel's map, for which it took my brand new laptop 30 minutes to calculate the Godel number for the formula '0=0' (it's7,286,659, if we map the language symbols '0' and '=' to 0 and 1 respectively, in case anybody's interested).
Godel's map produces much smaller numbers, but that gives no practical advantage, as the numbers still become enormous very very quickly, and are usually impractical to calculate anyway.
Neither map is a surjection onto the natural numbers. Both are primitive recursive.
Both can be simply and naturally extended to map proofs to natural numbers.
So I wonder why Godel chose such a complex approach, rather than Hofstadter's simple and (to me) obvious one. This is made more intriguing by the fact that, in discussions of Godel's proof, I have seen the map he defined described as one of the most brilliant insights in it.
The only practical advantage of Godel's map over Hofstadter's that I can think of is that Godel's copes quite naturally with a language that has an infinite alphabet, which for instance allows for an unlimited number of different one-character symbols for variables, functions and predicates. Hofstadter's approach requires a finite alphabet - in fact his use of three-digit codes places a limit of 1,000 on the number of different characters that can be used.
However, I think the limitation of Hofstadter's map is easily overcome by using the prime character as many times as necessary, so that:
x, x', x'', x''', ... are names of different variables
f, f', f'', f''', ... are names of different functions
p, p', p'', p''', ... are names of different predicates
If that is correct then I am left perplexed as to why Godel chose such a complicated and confusing map. I am very impressed by his map. It would take a brilliantly creative mind to have thought of it. But I just can't see why he didn't take the simple route. Is there some flaw in or limitation of Hostadter's approach that I am missing?