4 ms·

I don't think that this problem is even computable, since the functions could be arbitrarily complex. If you restrict the nature of the functions e.g. "polynom

I don't think that this problem is even computable, since the functions could be arbitrarily complex. If you restrict the nature of the functions e.g. "polynomials of degree at most d", then the answer depends on the restriction. For the polynomial of degree <= d case the solution is d+1 inputs, every polynomial of degree at most d is uniquely determined by d+1 points.

OJFord 6y ago
I'm having flashbacks to middle school when this was a (childish and easy, I thought, because we were 12 or whatever, not 6) exercise in a maths lesson. I vividly recall facetiously making this point, that for all we knew it was the 'number machine' (as I think the teacher called them) that responded 'as described for the inputs shown, and zero for all others', or something; that 'it sure looks like 2x, but we can't possibly know for all numbers'. If I'd been told the machines were linear I would have learnt something (probably, hard to recall one's knowledge at a specific time) and shut up. Alas, I was sent out...
- mcny 6y ago
  I had a similar experience in eighth grade with introduction to trigonometry. The teacher put in 0, 30, 60, 90, ... on the x axis and sine (x) on y. Then they began to join them with a beautiful curve. I protested and inquired how we can just join those dots seemingly on faith. The teacher just ignored me in spite of my repeated protests.
OJFord 6y ago
Sure, but it's bounded by human creativity, and there's anyway a difference between reliably and deterministically computing the function, and a sort of approximation with repeated guesses, or reaching a certain confidence. I only have vague recollections of numerical analysis, I remembered the Newton-Raphson method (no good: we don't have an oracle for f'(x), just f(x)) and stumbled into the Runge-Kutta Wikipedia page which I'd forgotten about (also no good). But it seems like a good strategy would be to test one number, guess assuming constant, test a second, guess assuming linear, test a third, guess assuming first order polynomial, and so on. In the presence of step changes or the like though I suppose there's nothing you can do.
- ThreeFx 6y ago
  > But it seems like a good strategy would be to test one number, guess assuming constant, test a second, guess assuming linear, test a third, guess assuming first order polynomial, and so on. You are still implicitly assuming that the function is continuous. There are a lot of nowhere-continuous functions, e.g. the sawtooth function. Or more interestingly, Conway's base13 function, which takes on every real number in every interval. Also what about continuous non-polynomials? e.g. exponentials, logarithms, sine/cosine etc.?
taejo 6y ago
If the functions are restricted to polynomials with non-negative integer coefficients, you only need 2 inputs regardless of degree. Proof left as an exercise to the reader.

OJFord 6y ago

I'm having flashbacks to middle school when this was a (childish and easy, I thought, because we were 12 or whatever, not 6) exercise in a maths lesson. I vividly recall facetiously making this point, that for all we knew it was the 'number machine' (as I think the teacher called them) that responded 'as described for the inputs shown, and zero for all others', or something; that 'it sure looks like 2x, but we can't possibly know for all numbers'. If I'd been told the machines were linear I would have learnt something (probably, hard to recall one's knowledge at a specific time) and shut up. Alas, I was sent out...

mcny 6y ago
I had a similar experience in eighth grade with introduction to trigonometry. The teacher put in 0, 30, 60, 90, ... on the x axis and sine (x) on y. Then they began to join them with a beautiful curve. I protested and inquired how we can just join those dots seemingly on faith. The teacher just ignored me in spite of my repeated protests.

OJFord 6y ago

Sure, but it's bounded by human creativity, and there's anyway a difference between reliably and deterministically computing the function, and a sort of approximation with repeated guesses, or reaching a certain confidence. I only have vague recollections of numerical analysis, I remembered the Newton-Raphson method (no good: we don't have an oracle for f'(x), just f(x)) and stumbled into the Runge-Kutta Wikipedia page which I'd forgotten about (also no good). But it seems like a good strategy would be to test one number, guess assuming constant, test a second, guess assuming linear, test a third, guess assuming first order polynomial, and so on. In the presence of step changes or the like though I suppose there's nothing you can do.

ThreeFx 6y ago
> But it seems like a good strategy would be to test one number, guess assuming constant, test a second, guess assuming linear, test a third, guess assuming first order polynomial, and so on. You are still implicitly assuming that the function is continuous. There are a lot of nowhere-continuous functions, e.g. the sawtooth function. Or more interestingly, Conway's base13 function, which takes on every real number in every interval. Also what about continuous non-polynomials? e.g. exponentials, logarithms, sine/cosine etc.?

taejo 6y ago

If the functions are restricted to polynomials with non-negative integer coefficients, you only need 2 inputs regardless of degree. Proof left as an exercise to the reader.