If you believe that f(x) = |x| is a "formula" giving the distance of a real number from zero, it's just as conditionally defined as (but less infinite than) the infinite lookup table you hypothesize.
On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.
If you allow a formula to be an infinite look-up table, then the statement "every [always halting] algorithm is a fixed formula" becomes true, but, I think, almost meaningless—it just says that the algorithm produces an output for every input. This is what I meant by saying:
This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'.
> On a more fun-fact note, there was a result some years ago expressing pi as an infinite series in powers of 16, with the headlining implication being "it may be possible to calculate the nth digit of pi (in base 16, or other powers of 2) directly, without needing to know the preceding digits" (I don't know the state of things since then, and details may have been jumbled in my memory). I suspect that there are implications for the puzzle you pose.No 'may' about it—it is possible to find the hexadecimal (and thus binary, 'quaternary', or octal, but not higher) digits using this algorithm. However, the discoverers explicitly disclaim its utility for finding decimal digits of pi in this way, and, indeed, say that no such 'look-ahead' algorithm is known (see p. 55 of http://link.springer.com/article/10.1007%2FBF03024340).
You object to my characterizing the pi-reading function you describe as an infinite lookup table. But it can't be implemented as an "intuitive" algorithm either. No matter how you code a function to solve that problem, it will always be trivial to provide input that your function cannot handle (if you have a representation of pi that you search, then you're relying on an infinite lookup table. If you calculate pi on the fly, you won't be able to handle large numbers as input). So I don't see why a defective (because you don't have enough time, or space, to run it) algorithm tranforming into a defective (because you don't have enough space to store it, but hey, time is no longer a concern) formula is a big problem for the equivalence between algorithms and formulae.
Also, I have to note that you've referred to the following mathematical result:
pi = \sum_{k=0}^\infty (16^{-k} * [4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6)])
as an "algorithm" instead of a "formula" ;)I'm sorry; you're quite right, and I was wrong.
> No matter how you code a function to solve that problem, it will always be trivial to provide input that your function cannot handle (if you have a representation of pi that you search, then you're relying on an infinite lookup table. If you calculate pi on the fly, you won't be able to handle large numbers as input).
I'm not sure why you say that I won't be able to handle large numbers as input. It might take a long time (like, a universe-endingly long time), but so would printing out the decimal expansion of 10↑↑10 (https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation), and I don't think that anyone would claim that that means that exponentiation algorithms "can't handle" this kind of exponentiation. (I dunno; maybe people would claim that.)
> So I don't see why a defective (because you don't have enough time, or space, to run it) algorithm tranforming into a defective (because you don't have enough space to store it, but hey, time is no longer a concern) formula is a big problem for the equivalence between algorithms and formulae.
My problem is that I think that there is no such equivalence, unless the definition of 'formula' is made so broad as to be essentially synonymous with 'algorithm'—at which point it's true but un-interesting. All I am arguing is (as a constructivist would) that it is worthwhile to maintain meaningful distinctions.
> Also, I have to note that you've referred to the following mathematical result `pi = [elided]` as an "algorithm" instead of a "formula" ;)
I did not mean to do that; I was referring to the process of using that formula (which is, as it were, an 'inert' object) to produce hexadecimal digits as an algorithm.
This is probably true for some very weak definition of the terms, but not, I think, in any sense that a random person would recognise as a 'formula'. For example, what is the formula for the algorithm "on input `n`, output the first position in the decimal expansion of `pi` at which a copy of the decimal expansion of `n` begins"?