# Does anyone know of any programmes that can find a function from a known input and output?

The outputs I'm getting are only 2x the length of the input strings so any kind of brute force programme would be fine. Thanks.

• That's not possible in general, by an argument similar to that for this question: we can make a counterexample where sucess would be a break of a cryptographic primitive that is trusted secure. For affine functions (including linear, CRCs..) see this answer. Software recommendation is not really on-topic – fgrieu May 4 '20 at 12:11
• Maybe in some specific cases, you can use machine learning. It wouldn't give you a specific function per se but would give you an approximation. – Curious Mind May 4 '20 at 12:39
• @HasanIqbal True, but I guess you would have to train it somehow. That might that you have to have a set of input strings, algorithms and output strings put into the neural network. Or do you think you can train it using just a large set of inputs and outputs? – Maarten Bodewes May 4 '20 at 14:54
• @MaartenBodewes Although I'm no expert in ML, I think that's the essence of training. Give it a set of input and corresponding output, ML algorithms would basically try to 'fit the curve' as best as it can. – Curious Mind May 4 '20 at 15:44
• It is fascinating because, as described in the comments above, there is an impossibility in general to reveal functions, and, at the same time, it is also impossible in general to hide a program that realizes a computable function: the known program obfuscation problem (boazbarak.org/Papers/obfuscate.pdf.) – McFly May 5 '20 at 1:29

Recovering an arbitrary function $$f:M \rightarrow N$$ from samples $$x_i, f(x_i)$$ is clearly impossible without additional information unless the given $$x_i$$ cover $$M$$ or unless $$N$$ is of size one, since an arbitrary continuation can be chosen on the remaining inputs. By the same token, it is trivial to find some function that reproduces the input-output behaviour of $$f$$ (for instance one may just pick a function that takes inputs outside the given values to some constant output in the codomain of the function).