Tortoise: The first type of search-the non-chaotic type-is exemplified by
the test involved in checking for the Goldbach property. You just look
at primes less than 2N, and if some pair adds up to 2N, then 2N has
the Goldbach property; otherwise, it doesn't. This kind of test is not
only sure to terminate, but you can predict BY WHEN it will terminate,
as well.
Achilles: So it is a PREDICT ABLY TERMINATING test. Are you going to tell
me that checking for some number-theoretical properties involves tests
which are guaranteed to terminate, but about which there is no way to
know in advance how long they will take?
Tortoise: How prophetic of you, Achilles. And the existence of such tests
shows that there is intrinsic chaos, in a certain sense, in the natural
number system.
Achilles: Well, in that case, I would have to say that people just don't know
enough about the test. If they did a little more research, they could
figure out how long it will take, at most, before it terminates. After all,
there must always be some rhyme or reason to the patterns among
integers. There can't just be chaotic patterns which defy prediction!
Tortoise: I can understand your intuitive faith, Achilles. However, it's not
always justified. Of course, in many cases you are exactly right-just
because somebody doesn't know something, one can't conclude that it
is unknowable! But there are certain properties of integers for which
terminating tests can be proven to exist, and yet about which it can also
be PROVEN that there is no way to predict in advance how long they will
take.
Achilles: I can hardly believe that. It sounds as if the devil himself man-
aged to sneak in and throw a monkey wrench into God's beautiful
realm of natural numbers!
Tortoise: Perhaps it will comfort you to know that it is by no means easy, or
natural, to define a property for which there is a terminating but not
PREDICTABLY terminating test. Most "natural" properties of integers
do admit of predictably terminating tests. For example, primeness,
squareness, being a power of ten, and so on.
Achilles: Yes, I can see that those properties are completely straightfor-
ward to test for. Will you tell me a property for which the only possible
test is a terminating but nonpredictable one?
Tortoise: That's too complicated for me in my sleepy state. Let me instead
show you a property which is very easy to define, and yet for which no
terminating test is known. I'm not saying there won't ever be one
discovered, mind you-just that none is known. You begin with a
number-woul~ you care to pick one?
Achilles: How about IS?
Tortoise: An excellent choice. We begin with your number, and if it is ODD,
we triple it, and add 1. If it is EVEN, we take half of it. Then we repeat
the process. Call a number which eventually reaches 1 this way a
WONDROUS number, and a number which doesn't, an UNWONDROUS
number.
(^400) Aria with Diverse Variations