Is the author Hofstadter cheating in his argument on completeness appling Cantor's Diagonal Proof to Gödel's (natural number) Numbering? Hofstadter in his book Gödel, Escher, Bach is 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 the
  natural 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?
 A: Perhaps a further example will serve to confuse you even more.
Consider Euclid's classical argument for the infinitude of primes. Suppose $p_1,\ldots,p_n$ is a finite list of all primes. Then $P = p_1 p_2 \cdots p_n + 1$ must have a prime factor different from $p_1,\ldots,p_n$, since by design, none of these can be factors of $P$.
Euclid's argument is also a sort of "diagonal argument", since $P$ is constructed to be "different" than the given list of primes; though $P$ is not a prime itself, so this is actually a "generalization" of the diagonal argument.
When people say "diagonal argument", they don't mean Cantor's particular proof of $\mathbb{Q} < \mathbb{R}$, but rather some idea, some proof technique, which is only loosely defined. And yet, the concept is useful, and the experienced mathematician will be quite content when told that a certain statement "can be proved by diagonalization"; if she really wanted and had the time, she could probably reconstruct the argument.
Oftentimes, the set to which an element is proven not to belong, this set is indeed countable. But Cantor's argument was generalized by Cantor himself to show that $S < 2^S$, for any $S$ (modern technicalities ignored). The power of the method lies in its general applicability.
I vividly recall taking a course on the theory of computation. One section was devoted to "reducibility and diagonalization". The section gave some example of these very important concepts and techniques. Perhaps something of that sort will help you make up your own mind whether mathematicians are justified when they draw attention to the similarity between Cantor's original argument and ones like Hofstadter mentions.
A: Hofstadter is referring to diagonalisation in general, as also used by Gödel. He doesn't mean the specific diagonalisation argument that Cantor used to prove the uncountability of the real numbers.
A: I just reread the section again, and you are correct that it is not a literal diagonalization, but rather mimics the approach of the Cantor diagonalization, in that it establishes that one item which should be in a list of items cannot be, and thus the list can never be complete. According to this Wikipedia entry on the diagonal lemma, this idea is called "diagonal" due to this resemblance to Cantor's argument. Presumably Hofstadter is using diagonal in this sense.
A: The argument he gives is the standard proof that there are functions that are not primitive recursive. The same argument is given in here, and in textbooks. So no, he's not cheating.
You should read the section "What does a diagonal argument prove?" on p-$422$. You start with a list, and then show that there must be an element that isn't in the list. In Cantor's argument, this is used as a proof by contradiction: the supposition that you could create a countable list of all real numbers must have been false. In the present case, the list was all primitive recursive functions, and what the argument shows is simply that there are functions which are not primitive recursive. In Cantor's argument, the element produced by the diagonal argument is an element that was meant to have been on the list, but can't be on the list, hence the contradiction. In the present case, all we're trying to show is that there are functions that aren't on the list.
A: To 'see the diagonal', form an image in your mind of a two-dimensional matrix, indexed by the natural numbers on both dimensions (hence infinite on both dimensions).  Let the matrix entry (i, j) be the pair [$B_i$, #j], where $B_i$ is (the interpretable source-coded of) the primitive-recursive program 'Blueprogram[i]', and #j is (the textual value of) the number j.  If you pick an arbitrary entry (i, j), you can interpret $B_i$ operating on argument #j and get back a value.
Then Hofstadter invites you to consider this program:
Bluediag(N) = { Let p = entry($B_N$, N); let y = [result of interpreting p]; return y + 1; }
The 'diagonalization' is the fact that N is being used as the value of both i and j to get the entry (i, j).
