What does it mean "Predicates should not modify their state due to a function call"?

Let's consider the algorithm std::count_if as an example. It traverses a range and counts how often a given predicate evaluates to true. Further assume we want to check how many elements in a container are smaller than a given number, e.g. 5 or 15.

A predicate can be many things. It just has to be callable. It can be a functor:

struct check_if_smaller {
    int x;
    bool operator()(int y) const { return y < x; }
};

You can create different instances of that predicate, e.g. these two

check_if_smaller a{5};
check_if_smaller b{15};

can be used to check if numbers are smaller than 5 or 15 respectively:

bool test1 = a(3);  // true because 3 < 5
bool test2 = b(20); // false because 20 is not < 15

The member x is the state of the predicate. Typically this should not change when the predicate is applied (by calling its operator()).

From wikipedia:

In mathematical logic, a predicate is commonly understood to be a Boolean-valued function P: X→ {true, false}, called the predicate on X. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory.

Sloppy speaking, a predicate is a function mapping something to a boolean. The fact that we use a functor that is not just a function but a function object with a state can be considered as an implementation detail, and repeatedtly evaluating the same predicate for same input is commonly expected to yield the same result. Also, algorithms make this assumption and nothing really prevents them from copying the predicate you pass (actually the standard explicitly permits them to do so). If evaluating the predicate would alter its internal state, the algorithm may not work as expected.

In laymen terms, a state in a predicate is a data member. A predicate changing the state means that the member get's changed during the algorithm execution and that change is going to affect predicate behavior.

The reason to avoid this is the fact that algorithms are under no obligation to keep a single instance of a predicate. They might easily be copied around, and state changed in one copy, will not be shared with a state in another copy. As a result, program will behave unexpectedly (for someone expecting the state change to be in effect).

Essentially what standard says that predicate should act like a pure function (in mathematical terms), i.e. its returning value should be dependent on input alone.

The mention of state because predicates can be copied or can be invoked in different threads, which depends on implementation and platform behavior. For lambda's and other invokable objects which aren't functions this may mean unordered access to the storage, captured by reference, or access different values if they were captured by value. For a function, it means that any side-effects (including change of static variables) may result in problems.

If a predicate for sorting would return different results for same pair, then some sort algorithms become invalid.