In Gödel, Escher, Bach Chapter XIII: BlooP and FlooP and GlooP, Douglas Hofstadter states that:
This puts us in the uncomfortable position of asserting that people can calculate Reddiag[N] for any value of N, but there is no way to program a computer to do so.
How come this is true? What if
Reddiag[N] = 1 + Reddiag[N]? I understand how this is not computable, but how is it calculable? Is the idea that a person could notice that this is a sum of an infinite series of 1's, and either calculate that the answer is "infinity" or something like "-1/12" and therefore terminate?
Reddiag is defined as
Reddiag[N] = 1 + RedProgram[#N][N], where
RedProgram is any function written in a Turing complete language that takes one integer as an input, and we know that it is guaranteed to terminate with all inputs.