Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a function $f$ with the property $f\circ f=f$. What would be a reference?

My application is a cryptographic security reduction. An example would be an algorithm which on input $X\in\{0,1\}^*$, outputs $1^{|X|}$.

Besides identity, an algorithm implementing $X\mapsto|X|$ in one of $\Bbb Z$, $\Bbb Q$, $\Bbb R$, $\Bbb C$ also comes to mind.

Stationary algorithm or circular algorithm would do, but neither googles. In my experience that means quickly it will google here, bringing circularity to a new level!


2 Answers 2


In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.

  • 4
    $\begingroup$ In some contexts, this is also called a projection. $\endgroup$ Jun 2, 2020 at 8:27

Ilkka Törmä has already given the answer that $f$ is an idempotent function.

You might want to be aware of the concept of fixed-points.

A point $c$ is a fixed-point for $f$ if $f(c) = c$, and hence

$$f(f(c)) = f(c) = c.$$

A set of fixed-points is often called a fixed set.

In your scenario, the output of $f$, or image of $f$, is a fixed set itself.

  • $\begingroup$ Ah. So correct me if I'm wrong, but my class of algorithms is those which output is a fixed set for them. While idempotent algorithm is shorter and attested, I'm happy to have a short name for the set of outputs of these algorithms: their fixed set. $\endgroup$
    – fgrieu
    Jun 3, 2020 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.