Suddenly, there is this snag: this function Greendiag [N] may not have a well-defined output value for all input values N. This is simply because we have not filtered out the nonterminator programs from Pool F, and therefore we have no guarantee that we can calculate Greendiag [N] for all values of N. Sometimes we may enter calculations which never terminate. And the diagonal argument cannot be carried through in such a case, for it depends on the diagonal function having a value for all possible inputs.

In other words, Hofstadter is saying that if a given function is not known to terminate for even one possible input value (he calls this a "Green" function), then another function that uses it is "incalculable" (in FlooP) and therefore not well defined (in FlooP). I will come back to this in a moment, but it's what Hofstadter goes on to next that really caught my attention. (Bear with me here; we have to go through some theory, but it's coming back around to practical matters and Perl in a bit.)

In order to perform Cantor's diagonal trick (and thus construct a Godel function, a function which by definition is not representable in the system in question, in this case FlooP or any Turing-equivalent language), Hofstadter posits a helper function which solves the halting problem and filters the collection of all possible FlooP functions based on whether they terminate. He then performs the Cantor diagonal trick on only the "Red" programs (those that are known to terminate for all possible inputs), concluding...

We define Reddiag [N] = 1 + Redprogram{#N} [N] and in an exact parallel to Bluediag, we are forced to conclude that Reddiag [N] is a well-defined, calculable function of one variable which is not in the catalog of Red Programs, and hence not even calculable in the powerful language of FlooP. Perhaps it is time to move on to GlooP?

Whoah! Non sequiteur! Unless I am missing some quite major point. (Which, admittedly, is possible. Feel free to point out what I'm missing. Meanwhile...)

As near as I can determine, the truly big leap is from Reddiag not being in the catalog of Red programs (those known to terminate for all possible inputs) to its therefore being incalculable in FlooP. First off, there is the obvious point that it could be Green, i.e., not terminate for some possible inputs; it could certainly nevertheless terminate for many possible inputs, or, even, all but one. (Indeed, it could terminate for all Red inputs, but not for Green inputs; this would be consistant with what I know about the halting problem.) Further, and worse, Hofstadter asserts that Reddiag is "a well-defined, calculable function", in spite of the fact that it depends for its implementation on a termination-tester -- which, if you know anything about the halting problem, is *known* not to terminate for all possible inputs. It seems quite reasonable then that Reddiag would not be in the list of Red programs. It would be Green.

Additionally, the author makes no attempt to explain why the set of all Red programs is interesting, except in that the Cantor diagonal trick can be applied to it; in particular, he assumes that demonstrating the incompleteness of the set of Red programs is necessarily equivalent to demonstrating the incompleteness of FlooP.

Now, all of that said, I don't want to come off as too harsh here. I understand that Hofstadter did not set out to put down a rigorous proof, that such had been done by Godel and others previously and that his goal in talking about it at all is make a point that ties in to what he ultimately wants to talk about (artificial intelligence, regarding which incidentally his ideas are quite strange, but that is another topic). So I'm not saying all this just to poke holes in his proof of the incompleteness of FlooP. (Quite the contrary; I was willing to accept the incompleteness of FlooP without argument.) But I got to thinking about the mixup between Red functions and all FlooP functions, and then I looked back up to the first paragraph I quoted above (about Greendiag)...

Upon inspection it seemed to me (though this turns out to be wrong, but it lead me to something else) that the incompleteness of FlooP (or presumably any Turing-equivalent language), at least insofar as it is demonstrated by the Cantor diagonal line of reasoning as Hofstadter applies it, relies on that point: a function that may not terminate for even one possible input is not well-defined. So I started thinking about how this chain might be broken.

Hofstadter, of course, concluded that GlooP (the more powerful language) is a myth, that no more powerful language (where "powerful" is defined only in terms of what *can* be represented, not on the ease or efficiency of doing so) can be defined -- and this is by no means an unusual view. I prefer to think, however, that we only don't currently know *how* to define any more powerful language and that if we could, we are not at all sure we could implement a compiler or interpreter for it using the FlooP-equivalent languages we have available. (One could jump off here and discuss quantum computing, but I'll leave that for another thread.)

The first thing that sprung into my head, when I allowed myself to think about breaking that chain, is lazy evaluation.

My reasoning was this: lazy evaluation allows a function to return a result without finishing the details of the calculation or even knowing whether it will terminate. It is adequate to know *how* to perform the calculation; it is not necessary to finish *doing* it. Coming from a math background, I am accustomed to accepting as an answer for a problem something other than a simple number expressed in decimal notation. e.g., we can accept pi/4 as an answer, even though any attempt to express the result of that division in the usual fashion would never terminate -- i.e., mathematicians have in some sense bypassed the halting problem for centuries via lazy evaluation of a sort -- we know how to calculate pi (even though it would take forever to do so), so even though we've never finished doing so we accept answers based on it as well-defined.

Now, Perl6 is going to have at least some lazy evaluation, of lists at least if nothing else. For example, the following is perfectly cromulent (in principle; my syntax may have a bit or two of legacy Perl5 syntax in it by mistake, but don't let that distract from the principle):

  sub identity is lazy {
     my @i = 1..Inf;
     return @i[shift @_];
  }
[download]

Now, identity($n) will return $n for any natural value of $n, provided you have enough RAM for your particular chosen value of $n (and provided you've turned on the autopromote-to-bignums feature, if it's not on by default in Perl6). It's not the most efficient way to do so, but nevermind that. The compiler and/or interpreter may or may not optimize some of the inefficiency away, but for language theory we don't care about that either. In principle, there's no theoretical reason why we can't also do something like this:

   sub returnlazy is lazy {
       return map { 2*n } 1..Inf;
   }
   sub ntheven is lazy {
       my @evens = returnlazy();
       return @evens[shift @_];
   }
   my $se = ntheven(17);
   print "The seventeenth even number is $se.\n";
[download]

$seventeentheven might not be calculated per se until it its value is actually needed (for printing), but we know that it is well-defined and that coughing up the value is not a problem, in theory.

The first result of this, going back up to what I was saying above, is that it doesn't invalidate the incompleteness proof; if anything, it makes the proof cleaner, plugging up the hole Hofstadter's explanation left in his application of the Cantor diagonal, because it does away with the need to test for termination and construct a catalog of Red programs; with lazy evaluation, Cantor's infamous trick applies directly to the set of *all* functions in the language, including Green ones. However, since I am not aware of any proof to the effect that a (theoretical) language which is more powerful than FlooP would necessarily be complete, this in itself does not preclude the possibility that lazy evaluation could lead to GlooP.

Now, the other, less surprising news, is that this doesn't create GlooP. The reason it doesn't comes down to the nature of Turing equivalence: lazy evaluation can be "faked" in current languages in much the same way that (e.g.) linked lists can be "faked" in BASIC without pointers as such. It's a bargeload of extra work, but you can do it. Therefore, we're not enabling anything that wasn't already fundamentally possible.

However, the more I thought about lazy evaluation, the more I couldn't get away from how *useful* it would be anyway, especially when combined with multitasking: think in terms of functions that return running processes which are calcuating output, and calling code that can proceed to process that output as it is generated. As noted, this can be faked in current languages (certainly in Perl5) by forking and using some form or another of interprocess communication (e.g., sockets), but that requires the programmer to deal with a lot of details; lazy evaluation can tuck those details away under the hood and make it all automagical, at least in theory. Your function can define how to calcuate the list and so return the list lazily, and the calling code can process the first however many values off the list, until you stop it. It might be useful for more than just list generation, as well. Strings are trickier without core support, especially if you want to be able to do regular-expression matches against them (watch out for greediness!), but I get the idea that the general flexibility of Perl6 will be adequate to allow a module to make such things possible.

So there you go, another reason to be excited about Perl6.