next up previous contents
Next: Recursive and Recursively Enumerable Up: Encoding and Algorithms Previous: Encoding and Algorithms

Problem instances as strings, problem as language

By restricting consideration to boolean problems, and encoding instances of the problem by strings over a finite alphabet, we can transform the question of whether there exists an algorithm for solving a problem to whether or not a particular language is recursive [Hopcroft p. 177]. (A problem can be represented as the language of instance strings)