# Program Synthesis with Pragmatic Communication (@ arXiv 2020)

### Yewen Pu, Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-Lezama

Here's the deal. In program synthesis based on input-output examples, there's an obvious problem of massive ambiguity. For example, what is a function that takes the number 2 and returns 4? It could be $f_1(x) = 2x$, or $f_2(x) = 2 + x$, but it could also be $f_3(x) = 2$, $f_4(x) = 10 - 3x$, or $f_5(x) = 1073741834 - x^{30}$. It doesn't matter how many examples you give - being just a finite number of them, I can always come up with infinitely many weird functions that match them, and that are not what you want. How is a synthesizer supposed to guess?