Hofstatter on Cantor:
)((
Is the author Hofstadter cheating in his argument on completeness appling Cantor’s Diagonal Proof to Gödel’s (natural number) Numbering?
Asked 13 years, 7 months ago
Modified 8 years, 8 months ago
Viewed 1k times
1
Hofstadter in his book Gödel, Escher, Bachis describing Godel’s contradiction of sufficiently powerful versus complete. In the chapter 13 BlooP, FlooP, and GlooP he writes,
Now although completeness will turn out to be a chimera, TNT is at least complete with respect to primitive recursive predicates. In other words, any statement of number theory whose truth or falsity can be decided by a computer within a predictable length of time is also decidable inside TNT. (p418)
Hofstadter uses the previously introduced systems called TNT and BlooP as the base of his argument. He continues,
So the question really is, Can upper bounds always be given for the length of calculations [his definition of primitive recursive predicates]–or, is there an inherent kind of jumbliness to thenatural number system, which sometimes prevents calculation lengths from being predictable in advance? The striking thing is the latter is the case, and we are about to see why. […] In our demonstration, we will use the celebrated diagonal method by George Cantor, the founder of set theory. (p418)
Hofstadter’s proof begins with a set of functions understood to be primitive recursive functions called Blueprograms {#N}[N]. To my understanding this is an array with index {#N}, accepting the value [N] as an argument.
Then to form the proof (within the section titled “The Diagonal Method”) Hofstadter adds +1 to it, and finally assigns this value to a new function called Bluediag[N]:
Bluediag[N] = 1 + Blueprogram {#N}[N]
He concludes that simply by adding +1 to the set Blueprograms the new set (or superset) called Bluediag lies outside the realm of primitive recursive functions. (p420) Thus demonstrating it is likely impossible to test for primitive recursive functions.
This may all be well and good. If true–to my mind–its due to the paradoxical or loopy nature of recursion, and not to Cantor’s diagonal method for real numbers. My modest understanding of the orders of infinity says that adding +1 to infinity does not change the size of infinity. This is the Hilbert Hotel non-intuitive Paradox says infinity + infinity = infinity.
See also Why Doesn’t Cantor’s Diagonal Argument Also Apply to Natural Numbers?
Cite
Follow
CommunityBot
1
asked Nov 7, 2011 at 13:32
22111 silver badge88 bronze badges
- Doesn’t Hofstadter say explicitly that his presentation is not quite right? I remember reading words to that effect in the BlooP, FlooP and GooP discussion.
- I’m reading the book now. If he does, I haven’t found the passage.
- I’ll see if I can dig it up.
- I changed my comment. On rereading I noticed it was distractedly familiar to the Barber of Seville Paradox, “If he does, Then he doesn’t.” (^_^)
- Oh I see. I wondered why I just got a notification. That section is pretty dense. I’ll probably have to reread it in its entirety to find the relevant passage.
()
am I on the right track? I wonder? If not no worries, besides the mathematics befuddled Cantor himself.