Since we are using strings as a universal data type, the input to every problem that we consider is a string.
In order to talk about strings, we need an alphabet. The alphabet is given as part of the problem.
The string usually has a chosen form. For example, it might be a number or a list of numbers or a program written in Python or something else.
But it is always a string.
Since strings are finitely long, the input can never be infinitely long.
For functional problems, the output is also a string.
The output string typically has a special form as well. It can be a number, a list of numbers, a program, etc.
A functional problem is typically expressed as in the following example.
Input. A positive integer x (as a string)
Output. Either number −1 or an integer y where 0 < y < x where y is a divisor of x.
For a decision problem, the output is binary. It can be expressed as yes/no, true/false, 1/0, etc. Usually, it is yes or no.
There are two common ways of describing a decision problem. The first is similar to the description of a functional problem.
Input. An integer x where x > 1. (x is written in standard notation, such as 345.)
Question. Is x a composite number?
The second common way to describe a decision problem is by a set.
When thought of as a computational problem, set S of strings is the following problem.
Input. String x.
Question. Is x ∈ S?
The advantage of describing a decision problem as a set is that it is compact, and it makes some definitions and proof easy to express.
It is important to distinguish between problems and algorithms.
There can be many ways to solve a particular problem.
In some cases, there are no ways to solve a particular problem. We still need to be able to talk about the problem.
Some adjectives or verbs make sense for problems and some make sense for algorithms (or programs). Here is a sampling.
Be sure to use terminology about the correct sort of thing.