Next: Recursive and Recursively Enumerable
Up: Encoding and Algorithms
Previous: Encoding and Algorithms
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)
root
6/10/1998