2.7. Computational Problems


Functional problems

Normally, we think of a computer program as taking a string as an input. Start by choosing an input alphabet I and an output alphabet O. A functional problem is a function whose domain is I* and whose codomain is O*.

For example, a functional problem might to be to take a positive integer x (written using alphabet {0,1,2,3,4,5,6,7,8,9}) and to yield the value x2, written in the same alphabet. (It is allowed for the input and output alphabets to be the same.)


Decision problems

A decision problem is a function that takes a string and yields either yes or no.

Although you can think of a decision problem as a function, you can also think of it as a language. If L is a language, then, when thought of as a decision problem, L corresponds to the following function fL, called its characteristic function.

fL(x) = yes when xL
fL(x) = no when xL

Because of their simplicity, languages are useful types of problems for studying what can and cannot be computed.