3 ms·
>> Some things are trivial to specify but hard to code. Well, that's the point of automating the coding effort. The specification guides a search for a program
by YeGoblynQueenne 5y ago
>> Some things are trivial to specify but hard to code.
Well, that's the point of automating the coding effort. The specification guides a search for a program that satisfies it. In your hash table example there's no need to tell the synthesiser how to code the hash table, only what the hash table has to do.
The search of course can get very expensive and that's an important bottleneck in program synthesis. But, in principle, if the specification is correct, then a correct program is somewhere in the program search space and a search will eventually find it.
- YeGoblynQueenne 5y agoDid I accidentally say something offensive in the above comment?
- sbierwagen 5y agoJust reading the thread now, and the silent downvoters might be objecting to the "eventually" part. "Find the busy beaver program for a 20 state Turing machine" is easy to specify, but could take quadrillions of years to return a result.
- YeGoblynQueenne 5y agoThanks, that could be the reason. But it's also a truism. The only guarantee that can be given for a search procedure is that if a target exists, the search will find it. An infinite search space is an infinite search space and there is no search that can search it in finite time. Anyway that's the rules of the game for search-based program synthesis. The best that can be done is to guarantee that the search space contains the program. It's an important bottleneck and in my opinion is part of what has kept the field back from fully achieving its goals (which are diverse- and there are diverse sub-fields also).