<p>Ilkka Törmä has already given the answer that <span class="math-container">$f$</span> is an <em>idempotent</em> function.</p>

<p>You might want to be aware of the concept of
<a href="https://en.wikipedia.org/wiki/Fixed_point_(mathematics)" rel="nofollow noreferrer"><em>fixed-points</em></a>.</p>

<p>A point <span class="math-container">$c$</span> is a fixed-point for <span class="math-container">$f$</span> if <span class="math-container">$f(c) = c$</span>, and hence</p>

<p><span class="math-container">$$f(f(c)) = f(c) = c.$$</span></p>

<p>A <em>set of fixed-points</em> is often called a <em>fixed set</em>.</p>

<p>In your scenario, the output of <span class="math-container">$f$</span>, or
<a href="https://en.wikipedia.org/wiki/Image_(mathematics)" rel="nofollow noreferrer"><em>image</em></a> of <span class="math-container">$f$</span>, is
a <em>fixed set</em> itself.</p>

CC BY-SA 4.0
2020-06-03T11:38:08.767Z
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_.
fgrieu
CC BY-SA 4.0
2020-06-03T10:41:16.410Z
2020-06-03T10:41:16.410Z
John K.
<p>In mathematics we would say <span class="math-container">$f$</span> is an <a href="https://en.wikipedia.org/wiki/Idempotence#Idempotent_functions" rel="noreferrer"><em>idempotent function</em></a>. It's a widely known term and I suppose most TCS people should also recognize it.</p>

CC BY-SA 4.0
2020-06-02T08:27:26.243Z
In some contexts, this is also called a *projection*.
Emil Jeřábek
CC BY-SA 4.0
2020-06-02T08:14:37.773Z
2020-06-02T08:14:37.773Z
Ilkka Törmä
<p>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 <span class="math-container">$f$</span> with the property <span class="math-container">$f\circ f=f$</span>. What would be a reference?</p>

<p>My application is a cryptographic security reduction. An example would be an algorithm which on input <span class="math-container">$X\in\{0,1\}^*$</span>, outputs <span class="math-container">$1^{|X|}$</span>.</p>

<p>Besides identity, an algorithm implementing <span class="math-container">$X\mapsto|X|$</span> in one of <span class="math-container">$\Bbb Z$</span>, <span class="math-container">$\Bbb Q$</span>, <span class="math-container">$\Bbb R$</span>, <span class="math-container">$\Bbb C$</span> also comes to mind.</p>

<hr>

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

<cc.complexity-theory><terminology>
Adjective for: algorithm that outputs its input if it is one of its outputs?
fgrieu
# Adjective for: algorithm that outputs its input if it is one of its outputs?

(Asked by: username_0 on 2020-06-02)

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!

**Tags:** cc.complexity-theory, terminology

---

## 2 answers

### Answer by username_2 on 2020-06-02. Score: 9 | Accepted answer

In mathematics we would say $f$ is an [*idempotent function*](https://en.wikipedia.org/wiki/Idempotence#Idempotent_functions). It's a widely known term and I suppose most TCS people should also recognize it.

> **Comments:**
> **username_3**: In some contexts, this is also called a *projection*.  

---

### Answer by username_1 on 2020-06-03. Score: 1

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*](https://en.wikipedia.org/wiki/Fixed_point_(mathematics)).

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*](https://en.wikipedia.org/wiki/Image_(mathematics)) of $f$, is
a *fixed set* itself.

> **Comments:**
> **username_0**: 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_.  

---

