[D] Program synthesis and Godel numbering
I had a little thought.
If we were to construct a godel numbering of a language then we can be sure that any random program we generate is valid.
There is such a language called Jot. It consists of a binary string which maps to the combinatory logic.
https://www.nyu.edu/projects/barker/Iota/
A compiler taking us from unlambda to jot exists:
https://tromp.github.io/cl/lazy-k.html
So one could take all the programs written in unlambda and use them as training material, rather than using a custom domain-specific language. Also, it is possible to map from various other languages to unlamda. So we have a pipe all the way down to a representation that has no possible syntax errors.
Where every string represents a valid program we do not have to worry about invalid syntax. We can simply evaluate the program for a limited time and examine the output.
As well as applying this technique to the existing program synthesis techniques you could also construct a GAN.
Then use the manifold of pre-existing programs constructed by it to inform the search for useful programs.
I’m sure this is all pie in the sky, but I have to let these ideas out onto the internet or I start to self destruct!
submitted by /u/MemeBox
[link] [comments]