But it seems likely that as one increases t , no ordinary Turing machine or cellular automaton will ever be able to guarantee to solve the problem in a number of steps that grows only like some power of t .

The method based on IntegerDigits in the previous two notes can be improved (notably by power tree methods), but apparently about Log[t] steps are always needed.

And in the 1990s Ivan Korec and others showed that it could be done just with Mod[Binomial[a + b, a], k] with k = 6 or any product of primes—and that it could not be done with k a prime or prime power.

Ackermann functions A convenient example is f[1, n_] := n; f[m_, 1] := f[m - 1, 2] f[m_, n_] := f[m - 1, f[m, n - 1] + 1] The original function constructed by Wilhelm Ackermann around 1926 is essentially f[1, x_, y_] := x + y; f[m_, x_, y_] := Nest[f[m - 1, x, #] &, x, y - 1] or f[m_, x_, y_]:= Nest[Function[z, Nest[#, x, z - 1]] &, x + # &, m - 1][y] For successive m (following the so-called Grzegorczyk hierarchy) this is x + y , x y , x y , Nest[x # &, 1, y] , .... f[4, x, y] can also be written Array[x &, y, 1, Power] and is sometimes called tetration and denoted x ↑ ↑ y .

Connections to formal power series and to substitution systems (see page 891 ) were studied in the 1960s.

Computing powers [of numbers] The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]] (related to the Horner form for the base 2 representation of t ). … However, the straightforward method for converting a t -digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as FixedPoint[Flatten[Map[If[# < k, #, With[ {e = Ceiling[Log[k, #]/2]}, {Quotient[#, k e ], With[ {s = Mod[#, k e ]}, If[s  0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}] The pictures below show stages in the computation of 3 20 (a) by a power tree in base 2 and (b) by conversion from base 3.

And indeed in the end the Principle of Computational Equivalence encapsulates both the ultimate power and the ultimate weakness of science.

At times the role of mathematics in science has been used in philosophy as an indicator of the ultimate power of human thinking.

At present, the most intense overall artificial radio emission from the Earth is probably the 50 or 60 Hz hum from power lines. The most intense directed signals are probably from radars (such as those used for ballistic missile detection) that operate at a few hundred megahertz and put megawatts of power into narrow beams. (Some such systems are however being replaced by lower-power phased array systems.)

And it is this that is ultimately responsible for the great power of the new kind of science that I describe in this book.