Latest update

# Do half-iterate functions exist for any function?

2018-05-08 04:27:15

For a given a deterministic unary function,

$$f(x) = y$$

A half-iterate function g(x) for f(x) is one which satisfies the following:

$$g(g(x)) = f(x)$$

For any f(x), does there exist a corresponding g(x) that is a half-iterate for f(x)?

It seems as though this must be true though I am having difficulty proving it.

Given that any deterministic unary function can be transformed into a directed graph (where $\overrightarrow {ab}$ denotes the edge pointing from a to b):

$$\forall \ \overrightarrow {ab} \in G, \ \ make \ \ f(a) = b$$

And likewise that any graph whose nodes have out-degree of exactly one can be transformed into a unary function -

$$\forall \ f(a) = b, \ add\ \overrightarrow {ab} \ to \ G$$

It seems obvious that one could create g(x) by replacing each edge $\overrightarrow {ab}$ with two others and a third node: $\overrightarrow {ac}$ and $\overrightarrow {cb}$. Inserting these two in place of the original edge does not change the importa