This seems to be making a somewhat arbitrary distinction—specifically a program that computes f(x) in some sort of a direct way, and a program that computes it in some less direct way (you call it a “lookup table”, but you seem to actually allow combining that with arbitrary decompression/decoding algorithms). But realistically, this is a spectrum—e.g. if you have a program computing a predicate P(x, y) that is only true when y = f(x), and then the program just tries all possible y—is that more like a function, or more like a lookup? What about if you have first compute some simple function of the input (e.g. x mod N), then do a lookup?
I agree that there is a spectrum of ways to compute f(x) ranging from efficient to inefficient (in terms of program length). But I think that lookup tables are structurally different from direct ways of computing f because they explicitly contain the relationships between inputs and outputs. We can point to a ‘row’ of a lookup table and say ‘this corresponds to the particular input x_1 and the output y_1’ and do this for all inputs and outputs in a way that we can’t do with a program which directly computes f(x). I think that allowing for compression preserves this important property, so I don’t have a problem calling a compressed lookup table a lookup table. Note that the compression allowed in the derivation is not arbitrary since it only applies to the ‘table’ part of the programme, not the full input/output behaviour of the programme.
if you have a program computing a predicate P(x, y) that is only true when y = f(x), and then the program just tries all possible y—is that more like a function, or more like a lookup?
In order to test whether y=f(x), the program must have calculated f(x) and stored it somewhere. How did it calculate f(x)? Did it use a table or calculate it directly?
What about if you have first compute some simple function of the input (e.g. x mod N), then do a lookup?
I agree that you can have hybrid cases. But there is still a meaningful distinction between the part of the program which is a lookup table and the part of the program which isn’t (in describing the program you used this distinction!). In the example you have given the pre-processing function (x mod N) is not a bijection. This means that we couldn’t interpret the pre-processing as an ‘encoding’ so we couldn’t point to parts of the program corresponding to each unique input and output. Suppose the function was f(x) =( x mod N )+ 2 and the pre-processing captured the x mod N part and it then used a 2xN lookup table to calculate the ‘+2’. I think this program is importantly different from one which stores the input and output for every single x. So when taken as a whole the program would not be a lookup table and might be shorter than the lookup table bound presented above. But this captures something important! Namely, that the program is doing some degree of ‘actually computing the function’.
> if you have a program computing a predicate P(x, y) that is only true when y = f(x), and then the program just tries all possible y—is that more like a function, or more like a lookup?
In order to test whether y=f(x), the program must have calculated f(x) and stored it somewhere. How did it calculate f(x)? Did it use a table or calculate it directly?
What I meant is that the program knows how to check the answer, but not how to compute/find one, other than by trying every answer and then checking it. (Think: you have a math equation, no idea how to solve for x, so you are just trying all possible x in a row).
This seems to be making a somewhat arbitrary distinction—specifically a program that computes f(x) in some sort of a direct way, and a program that computes it in some less direct way (you call it a “lookup table”, but you seem to actually allow combining that with arbitrary decompression/decoding algorithms). But realistically, this is a spectrum—e.g. if you have a program computing a predicate P(x, y) that is only true when y = f(x), and then the program just tries all possible y—is that more like a function, or more like a lookup? What about if you have first compute some simple function of the input (e.g. x mod N), then do a lookup?
I agree that there is a spectrum of ways to compute f(x) ranging from efficient to inefficient (in terms of program length). But I think that lookup tables are structurally different from direct ways of computing f because they explicitly contain the relationships between inputs and outputs. We can point to a ‘row’ of a lookup table and say ‘this corresponds to the particular input x_1 and the output y_1’ and do this for all inputs and outputs in a way that we can’t do with a program which directly computes f(x). I think that allowing for compression preserves this important property, so I don’t have a problem calling a compressed lookup table a lookup table. Note that the compression allowed in the derivation is not arbitrary since it only applies to the ‘table’ part of the programme, not the full input/output behaviour of the programme.
In order to test whether y=f(x), the program must have calculated f(x) and stored it somewhere. How did it calculate f(x)? Did it use a table or calculate it directly?
I agree that you can have hybrid cases. But there is still a meaningful distinction between the part of the program which is a lookup table and the part of the program which isn’t (in describing the program you used this distinction!). In the example you have given the pre-processing function (x mod N) is not a bijection. This means that we couldn’t interpret the pre-processing as an ‘encoding’ so we couldn’t point to parts of the program corresponding to each unique input and output. Suppose the function was f(x) =( x mod N )+ 2 and the pre-processing captured the x mod N part and it then used a 2xN lookup table to calculate the ‘+2’. I think this program is importantly different from one which stores the input and output for every single x. So when taken as a whole the program would not be a lookup table and might be shorter than the lookup table bound presented above. But this captures something important! Namely, that the program is doing some degree of ‘actually computing the function’.
What I meant is that the program knows how to check the answer, but not how to compute/find one, other than by trying every answer and then checking it. (Think: you have a math equation, no idea how to solve for x, so you are just trying all possible x in a row).