The first step to construct a general problem solver is to define what “problem” means .
There are 2 different groups of problems , in the first group we have a complete definition , in the second we know only a partial definition.
The most frequent is the first group . A simple example is the sorting problem . In this case we know what we want to obtain a sorted list of objects so we know the constraint for the list where every object must be <= of its successor. This description (usually known as specification of the problem) is itself a program and we can write it as ” for each possible list of objects the result is the sorted list”. The program directly defined by the specification usually is exponential and absolutely useless to solve practical problems so for this group solve the problem mean to find the temporal/spatial conversion of the problem. This is more easy than second group but in many cases is not absolutely easy .
In the second group we have all the partial defined , all the problems where we must find its definitions . A classic example is sequence prediction where given a sequence of bits like “01010101” we must predict the next bit value. In this case we must find first the best “specification” , the best program that fit the data and then we can operate like in the first group.
In all these 2 groups a problem is always defined as a program so to solve a problem means translate the “problem program” to the “best available program” .