Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Just 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.


Thanks, 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).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: