# Jump Over Left Menu

### Feasible Computability

#### Oliver Atkin

#### 1968

In pure mathematics one can often prove that some object
with certain properties exists; such a proof gives an
*existence theorem*. To find this object in a specific case
may be another matter. However, when one can in fact
do so, the reader might reasonably suppose that it
was *computable*. Unfortunately, this word has
come to have a technical meaning, that it is theoretically
possible to give an algorithm and a fixed integer N,
such that after at most N *steps* one can find the
object. Those who specialise in this sort of mathematics make in
addition a subtle distinction between *computable*
and *effectively computable*; roughly, possible by
some algorithm. and possible by the algorithm under current
consideration. But none of these words. existence, computable,
nor even effectively computable, means that one can actually do
it, in practice. here and now.

However the history of mathematics, and of number theory in particular,
is studded with examples of general conjectures made after the
examination of special cases actually calculated, and the generalization
finally proved (it may be easier to prove a wood than to prove trees).
A famous example is the law of quadratic reciprocity.
If *p* and *q* are different odd primes,
we write *(p/q) = 1* if the equation *x ^{2} = p + qy*
is soluble in integers

*x*and

*y*, and write otherwise

*(p/q) = -1*. Then the law is:

(p/q).(q/p) = 1if eitherporqis of the form4m + 1,(p/q).(q/p) = -1if bothpandqare of the form4m + 3.

This was certainly known to Euler, but was first proved by Gauss (who gave 8 proofs in all), and has since become the most proved theorem in number theory, around 200 proofs being known. In this case, of course, Gauss could certainly have found the law for himself (and possibly did).

Another more recent (1917) example is Ramanujan's conjecture that if

then
where
is interpreted as zero if *n/p* is not an integer.
Professor Mordell, who later proved this, tells me that he would probably not
have come across it on purely theoretical grounds. As a final example
we may cite the highly sophisticated conjectures of Birch and Swinnerton-Dyer
on elliptic curves, for which an extensive and informed computer attack
was needed; these still await proof.

The electronic computer has so vastly increased the possibilities of actual
calculation that one often needs to express the fact
(sometimes by no means trivial) that an object can now be calculated
in practice; the phrase *feasibly computable*,
suggested to me by John Leech, is here put forward.
Feasible computability is a strictly practical concept,
dependent on time and place, on the machine time required
in relation to the importance of the work, and so forth.
For this reason it is not susceptible to rigorous definition.

I give below an easy classical example which may help to crystallise these ideas. Before this, it should be stated that this article is solely concerned with computation as an empirical aid to discovery, and not with the further problems involved when electronically computed facts form an essential part of a final proof.

One of the most beautiful results of elementary number
theory is this: *given any two integers (positive or negative)
a
and b
with no common divisor greater than unity, there exist integers
x and y
such that ax + by = 1
*.

To prove this, consider for fixed *a* and *b* the (infinite)
class *C* of all numbers *(ax + by)* as *x* and *y* take all
integer values; let *d = ax _{1} + by_{1}
* be the least positive
member of

*C*. If

*d= 1*we have proved our theorem. We suppose then that

*d > 1*, and establish a contradiction. If

*d*does not divide

*a*, then

*a = qd + r*, with

*1 < r < d*, so that:

*r = a - qd = a - q(ax _{1} + by_{1}) = (1 - qx_{1}) a - (qy_{1}) b *

belongs to *C*, which is false since *r < d*.
Hence *d* divides *a*. Similarly *d* divides *b*.
But now *d > 1* is a common divisor of *a* and *b*,
contrary to hypothesis, and this contradiction proves the theorem.
Note that this proof of existence gives no clue at all as to how one
might actually find *x* and *y* with *ax + by = 1*.

Next, it is easy to prove that if x_{1}, y_{1} is *any* solution,
then the most general solution is

*x = x _{1} + bt, y = y_{1} - at; t = 0, ± 1, ± 2, . . .*

Hence there is *some* solution with *1 ≤ x ≤ b*
(and in fact only one), so that if we computability with *N = min(a,b)*.
Up to *N = 10 ^{2}
* by hand or 10

^{7}on Atlas, this may try all these

*b*values of

*x*we must come across a solution. This proves effective also be regarded as feasible (while Atlas could go further, this would not be justified in terms of machine time, in view of the algorithm below).

I show finally (without proof) the feasible method,
by which Stephen Muir has found solutions when *a* and *b* are as large
as 10^{100}, using the multi-length routines of Lunnon. It is best explained
by example, for which I choose *a = 64* and *b = 537*;
the numbers in brackets below are given to aid the explanation, and do not form part
of the calculation.

2(5) 64(1) 537(2) 8(3) 1(9) 14(6) 25(4) 1(7) 1(13) 3(10) 11(8) 3(11) 1(14) 2(12) 2(15) 0(16)

We start with our *a* and *b* (*a < b*) in (1) and (2),
and (3) and (4) are quotient and remainder for (2): (I). Next (5) and (6) are quotient and
remainder for: (1): (4), (7) and (8) for (4): (6), (9) and (10) for (6): (8), (11) and (12)
for (8): (10), (13) and (14) for (10): (12), and (15) and (16) for (12): (14).
When the remainder is 0 we stop, and the last divisor
(here (14) must be 1 if *a* and *b* have no common divisor.

2(5) 23(22) 193(23) 8(3) 1(9) 5(20) 9(21) 1(7) 1(13) 1(18) 4(19) 3(11) 0 1(17)

We now keep the numbers in the extreme columns except for the last one ((15)),
remove the middle columns, and replace the penultimate division by 1 (17) divides (13)
(in fact 1 here) (18) times with remainder O. In general (17) is always 1, and (18) equal
to (13). Next (19) = (18). (11) + (17), (20) = (19). (9) + (18), (21) = (20). (7) + (19),
(22) = (21). (5) + (20), (23) = (22). (3) + (21). The numbers 23 in (22) and 193 in (23)
are more or less our solution; in fact *64.193-537.23 = 1*.

This method takes more programming (about 40 Fortran statements) than the crude
method above, but its time
is of the order of
*log(min(a,b))* as opposed to *min(a,b)*.
As a proof of effective computability, the crude method exhibited
is the right proof because it is the simplest, and it is
permanently valid however large *a* and *b* are.
But, and this is the crux of the matter, it is only feasible for fairly
small *a* and *b*, while our final algorithm above
is feasible for much larger values, and with present machines no method is
feasible in general if *a* and *b* are as large as 10^{10100
}.

Of course the mathematician will recognise that this example is
slightly artificial, since the theory of the feasible method could be
used as a proof of existence and effective computability as well.
Effective computability clearly implies existence;
in some cases feasible computability may not, for one may *know* a feasible
method is right without having proved it!

The idea of feasible computability has always been of interest to some mathematicians.
Gauss in his Disquisitiones Arithmeticae (now translated into English,
which has regrettably replaced Latin as the lingua franca of international science)
often illuminates his general theorems both by small *examples* and by
feasible methods for large scale hand calculation. Nowadays a decision as to
feasible computability involves the possible use of computers, and the
mathematician who is not competent to assess what they might be able to do
for him may be unable to make it. A distinguished number theorist recently told
me that he would have tried to get some tables of interest to him computed,
but had assumed that a subsidiary operation would be impossibly slow.
I was able to assure him that I regularly performed this operation (by proxy) in
100 microseconds. So long as this kind of misapprehension exists, the Atlas Computer
Laboratory and other computer centres have a clear evangelical role to play.

Having decided that a computation is feasible, we must decide whether or not to perform it. The temptation to compute needlessly is particularly strong when a new machine makes a computation feasible for the first time. Swinnerton-Dyer is severe (though in brackets):

*(At the moment, most number theoretical calculations merely
pile up lists of integers in the manner of a magpie; they are neither designed to
produce valuable results nor capable of doing so.)*

While people may travel long distances to watch men lift heavy weights above
their heads, an international convention of bulldozer manufacturers in Mexico City
would be strictly a trade event. As a definitive and rigorous tour de force we may admire
Shanks and Wrench's calculation of the first 100000 decimal digits of π but be incurious
about the 100,001st digit. They wrote in 1961: *. . . say, in 5 to 7 years . . . a computation
of π to 1000000D will not be difficult*. The time has come, but nobody has done it;
this does not invalidate their prophecy, but merely indicates that their own work has
rendered such a computation pointless. I feel that 100000 is about right; anything
significant about the digits of π must show up by then (which might not have been true of 10000).
Of course this is a practical, and therefore subjective, judgment. But machine time is
finite, and one has to make these judgments continually.

The reader cannot expect me to quote an example of someone else's work that I regard as futile, but I can admit the possession of 2 cwt. of computed tables, of which at least 2 stone I have not even thought worth examining.

We are only considering here the value of computation in mathematics; naturally work may have value as new computational technique which has none as mathematics, and one should only condemn more of the same by the same method on a bigger machine when no reasonable hope of further discovery exists. In every attempt to discover the infinite by inspecting the finite, we have to decide when to stop computing and start thinking; this is a decision where the computer cannot replace the mathematician.

Finally, the computer has given a new lease of life to those mathematicians whose
interests lie in the direction of Hardy's quotation of Whitehead: *the large generalization,
limited by a happy particularity*. Before the electronic computer, man's powers of
calculation had been static for about 200 years, despite large individual variations.
A new discovery in an old subject by heuristic methods was hard to come by; those who
lived later had the advantage of more developed theory, but the disadvantage of
not being there first. Now they can add every few years an order of magnitude in their
numerical power. Each new generation of machines makes feasible a whole new range of
computations; provided mathematicians pursue these rather than merely break old records
for old sports, computation will have a significant part to play in the development of mathematics.
If mathematicians with machines cannot prove all that they conjecture, then at least
they will provide work for others, which may be the prime virtue of the 21st Century.