0
$\begingroup$

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?

Thanks :)

Update

The 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ What is "Reddiag"? $\endgroup$
    – nir shahar
    Mar 2 at 17:23
  • $\begingroup$ @nirshahar I have updates the answer, hope it is more clear right now $\endgroup$
    – spacemonkey
    Mar 2 at 17:45
  • 2
    $\begingroup$ Thanks! Can you please clarify the notation RedProgram[#N][N]? $\endgroup$
    – nir shahar
    Mar 2 at 17:53
  • 2
    $\begingroup$ Please don't use "Update" and don't just append stuff to the end. Instead, it would be better to revise the question so that it reads well for someone who encounters it for the first time. In particular, I encourage you to define RedDiag before you use that term for the first time. See cs.meta.stackexchange.com/q/657/755 $\endgroup$
    – D.W. ♦
    Mar 2 at 18:01

1 Answer 1

Reset to default
3
$\begingroup$

The passage in question has a standing assumption that RedProgram enumerates all computable total functions. Since Reddiag is total and different from every function enumerated by RedProgram, we conclude that it is not computable. The text continues to reach the conclusion that the standing assumption is false, by a standard argument in computability theory.

Let me also address your question about Reddiag[N] = 1 + Reddiag[N]. This is not possible because there is no natural number such that n = 1 + n.

Improve this answer
$\endgroup$
8
  • $\begingroup$ What do you mean by "total" functions? Terminates over all the inputs? Also, why in the book Reddiag is consider a "calculable", but not "computable" function? For instance this sentence "..._people_ can calculate Reddiag[N] for any value of N, but there is no way to program a computer to do so", what is meant by it? $\endgroup$
    – spacemonkey
    Mar 3 at 18:17
  • $\begingroup$ Yes, a function is total if it terminates on all inputs. The functiond Reddiag is called calculabe, by which the author means "humans can compute it", because humans can compute it. Sorry for a silly answer, but that's the meaning of "calculable". $\endgroup$
    – Andrej Bauer
    Mar 3 at 22:38
  • $\begingroup$ With "computability" I don't understand what exactly humans can and machines can't. For isntance, when BlooP (non-Turing complete) language was introduced, he showed Bluediag(N) = 1 + Blueprogram{#N}(N) function, where Blueprogram is a list of all BlooP programs. Then he showed using the diagonal method, how Bluediag is not part of BlooP functions, and therefore whilst it is calculable, machines can't compute it. My understanding the reason was that you could not implement recursion in BlooP due to its finite loops. At the same times humans could carry the computation forever. $\endgroup$
    – spacemonkey
    Mar 4 at 13:57
  • $\begingroup$ I thought he introduced FlooP (Turing complete language), because it is more "expressive" -- allows infinite loops. So now you could implement Bluediag and therefore compute it, by "computing" my understanding is that you calculate it forever, which is fine, because that's how it is defined. And I would assume by "calculable" it means that humans would do the same, calculate forever. $\endgroup$
    – spacemonkey
    Mar 4 at 14:13
  • $\begingroup$ Unless by "calculable" it means, that human would simply conclude that "Reddiag" and "Bluediag" can't terminate, whilst a machine would continue forever trying to find the answer. $\endgroup$
    – spacemonkey
    Mar 4 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.