A complete pool of all call-less FlooP programs which calculate
functions of exactly one input parameter, and which terminate for
all values of their input.Let us call these special FlooP programs Red Programs (since they all must
stop). Now, the diagonal argument will go through. We define
Reddiag [N] = 1 + Redprogram{#N} [N]
and in an exact parallel to Bluediag. we are forced to conclude that Red-
diag [N] is a well-defined, calculable function of one variable which is not in
the catalogue of Red Programs, and is hence not even calculable in the
powerful language FlooP. Perhaps it is time to move on to GlooP?
GlooP ...
Yes, but what is GlooP? If FlooP is BlooP unchained, then GlooP must be
FlooP unchained. But how can you take the chains off twice? How do you
make a language whose power transcends that of FlooP? In Reddiag, we
have found a function whose values we humans know how to calculate-the
method of doing so has been explicitly described in English-but which
seemingly cannot be programmed in the language FlooP. This is a serious
dilemma because no one has ever found any more powerful computer
language than FlooP.
Careful investigation into the power of computer languages has been
carried out. We need not do it ourselves; let it just be reported that there is
a vast class of computer languages all of which can be proven to have exactly
the same expressive power as FlooP does, in this sense: any calculation which
can be programmed in anyone of the languages can be programmed in
them all. The curious thing is that almost any sensible attempt at designing
a computer language ends up by creating a member of this class-which is
to say, a language of power equal to that of FlooP. It takes some doing to
invent a reasonably interesting computer language which is weaker than
those in this class. BlooP is, of course, an example of a weaker language, but
it is the exception rather than the rule. The point is that there are some
extremely natural ways to go about inventing algorithmic languages; and
different people, following independent routes, usually wind up creating
equivalent languages, with the only difference being style, rather than
power.
... Is a Myth
In fact, it is widely believed that there cannot be any more powerful
language for describing calculations than languages that are equivalent to
FlooP. This hypothesis was formulated in the 1930's by two people, inde-
pendently of each other: Alan Turing-about whom we will say more
later-and Alonzo Church, one of the eminent logicians of this century. It(^428) BlooP and F100P and GlooP