What's the optimal strategy for choosing inputs in order to guess the nature of the machine?
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.
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...
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.
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.
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.?