What can a computer learn from examples?
Peter Kugel · ACM SIGART Bulletin · 1976
About a year ago, I wrote an article that appeared in SIGART Newsletter [1] In that article, I asked "How well can computers generate programs from examples of what those programs are supposed to do?" My answer was that they cannot do very well If by "computers" we mean devices that only do total computations. I attempted to show that, under what seemed to me to be quite reasonable assumptions, a computer limited to doing total computations an a sequence of examples could only generate finitely many programs altogether and therefore (obviously) only finitely many programs that correctly accounted for the examples given.