3 ms·
What's the optimal strategy for choosing inputs in order to guess the nature of the machine?
by OJFord 7y ago
What's the optimal strategy for choosing inputs in order to guess the nature of the machine?
- ThreeFx 7y agoI 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 7y agoI'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 7y agoI 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 7y agoSure, 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 7y 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 7y agoIf 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.
- eternauta3k 7y agoInteresting question. If you have a prior distribution for the space of possible functions, you can find the input that minimizes the entropy of the posterior distribution (ie. makes it more like a delta and less like a uniform distribution)
- mar77i 7y agoI wanted to argue imps, dwarfs and other types of programs when I noticed that I was applying core wars terminology to a completely non core wars problem...