Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
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.
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.
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.
>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.
> 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.
The lookup table is part of the algorithm, and is not finite.
In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
It doesn't have to be part of the algorithm. It all depends on how you measure it.
Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
I am against statements like:
A: "X people don't know how to do Y"
B: "Why not do Z?"
A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"
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.
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.
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.
>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.
> 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.
Cool. I will assert a magic 8 ball that gives the correct answer. Are we done?
Yup, and everyone measures it to be part of the algorithm, otherwise you start getting nonsensical results.