[hcs]

Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.

[charcircuit]

We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.

[SkiFire13]

What you are stating is simply that any algorithm whose inputs are bounded can be solved in O(1) time with a lookup table. That's known and obvious, which makes it not interesting.

Moreover it only works with bounded inputs. If your input is unbounded (as is this case with multiplication over arbitrarily large numbers) then an infinitely big lookup table is just not possible because it's part of the algorithm and hence needs to be finite.

If infinitely-big lookup tables were allowed you could for example write an algorithm that solves the halting problem, just index into the lookup table for its solution. And actually you could do this for any problem! So any problem, even so called "non computable" ones, admit a solution that runs in time linear to their input. I hope you see that this is nonsensical and it's why lookup tables are considered part of the algorithm and hence need to be finite.

> You might not "want" something in a proof, but if it works then it works.

And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid, otherwise you're just talking about nonsense.

[charcircuit]

>And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid

It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.

[SkiFire13]

> You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.

Then sure, go ahead. Define your own model of computation, one not based on turing machines and which somehow allows for infinitely big lookup tables, and then see what great insight it provides you.

I wonder discoveries you will be able to make in a system where you can say that the solution of a problem is just its solution.

[lll-o-lll]

Cool. I will assert a magic 8 ball that gives the correct answer. Are we done?