Any program in which the decisions made at time t are impacted by the outcome of decisions made at time t-1. It learns.
A very simple construct within the field of Neural Networks is a Perceptron. It learns by adjusting weights given to different input values based on the accuracy of the result. It is trained with a known set of good inputs. Here is an article that covers the theory behind a single layer Perceptron network including an introduction to the the proof that networks of this type can solve specific types of problems:
If the exemplars used to train the perceptron are drawn from two linearly separable classes, then the perceptron algorithm converges and positions the decision surface in the form of a hyperplane between the two classes.
Here is a book chapter in PDF form that covers the topic. Here is an Excel Spreadsheet that explains a bit more with a concrete example. And finally, here is a beautiful Javascript Example that you can watch learn.