It seems that the relevant thing is not so much how many values you have tested as the domain size of the function. A function with a large domain cannot be explicitly represented with a small lookup table. But this means you also have to consider how the black box behaves when you feed it something outside of its domain, right? If it has some default “missing” value, that doesn’t complicate the conclusions much. But what if it is a lookup table, but the index is taken mod the length of the table? Or more generally, what if a hash function is applied to the index first? It seems that counting the number of unique output values taken by the function is more robustly lower-bounds its size as a (generalized) lookup table?
It seems that the relevant thing is not so much how many values you have tested as the domain size of the function. A function with a large domain cannot be explicitly represented with a small lookup table. But this means you also have to consider how the black box behaves when you feed it something outside of its domain, right?
This sounds right. Implicitly, I was assuming that when the black box was fed an x outside of its domain it would return an error message or at least, something which is not equal to f(x). I realise that I didn’t make this clear in the post.
But what if it is a lookup table, but the index is taken mod the length of the table? Or more generally, what if a hash function is applied to the index first?
In the post I was considering programs which are ‘just’ a lookup tables. But I agree that there are other programs that use lookup tables but are not ‘just’ tables. The motivation is that if you want simulate f(x) over a large domain using a function smaller than the bound given in the post, then the program needs to contain some feature which captures something nontrivial about the nature of f.
Like (simple example just to be concrete) suppose f(x)=[x(mod10)]^2 defined on all real numbers. Then the program in the black box might have two steps: 1) compute x(mod10) using a non-lookup table method then 2) use a lookup table containing x^2 for x=1 to 10. This (by my slightly arbitrary criteria) would count as a program which ‘actually computes the function’ since it has fixed length and its input/output behaviour coincides with f(x) for all possible inputs. It seems to me that if a blackbox program contains a subsection which computes x(mod10) then it has captured something important about f(x), more so than if the program only contains a big lookup table.
It seems that counting the number of unique output values taken by the function is more robustly lower-bounds its size as a (generalized) lookup table?
I think this is right. If you wanted to rule out lookup tables being used at any point in the program then this is bottlenecked by the number of unique outputs.
It seems that the relevant thing is not so much how many values you have tested as the domain size of the function. A function with a large domain cannot be explicitly represented with a small lookup table. But this means you also have to consider how the black box behaves when you feed it something outside of its domain, right? If it has some default “missing” value, that doesn’t complicate the conclusions much. But what if it is a lookup table, but the index is taken mod the length of the table? Or more generally, what if a hash function is applied to the index first? It seems that counting the number of unique output values taken by the function is more robustly lower-bounds its size as a (generalized) lookup table?
This sounds right. Implicitly, I was assuming that when the black box was fed an x outside of its domain it would return an error message or at least, something which is not equal to f(x). I realise that I didn’t make this clear in the post.
In the post I was considering programs which are ‘just’ a lookup tables. But I agree that there are other programs that use lookup tables but are not ‘just’ tables. The motivation is that if you want simulate f(x) over a large domain using a function smaller than the bound given in the post, then the program needs to contain some feature which captures something nontrivial about the nature of f.
Like (simple example just to be concrete) suppose f(x)=[x(mod10)]^2 defined on all real numbers. Then the program in the black box might have two steps: 1) compute x(mod10) using a non-lookup table method then 2) use a lookup table containing x^2 for x=1 to 10. This (by my slightly arbitrary criteria) would count as a program which ‘actually computes the function’ since it has fixed length and its input/output behaviour coincides with f(x) for all possible inputs. It seems to me that if a blackbox program contains a subsection which computes x(mod10) then it has captured something important about f(x), more so than if the program only contains a big lookup table.
I think this is right. If you wanted to rule out lookup tables being used at any point in the program then this is bottlenecked by the number of unique outputs.