Tal vez esta curiosidad califica? ...
Las tres funciones siguientes (los cuales mapa de los naturales a los naturales) forman una "completa de la base de" universal cálculo:
$$\begin{align}
f_0(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2} \\
f_1(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2 + 1}\\
f_2(n) & = [n>0] \left\lfloor\frac{n-1}{2}\right\rfloor
\end{align}$$
donde $[...]$ son Iverson soportes y $|n|_2 = \lfloor\log_2(n+1)\rfloor$ es el número de dígitos en el bijective base-2 representación de $n$. (Tenga en cuenta que $f_0, f_1$ es no-decreciente y $f_2$ es no creciente, mientras que $0$ es un punto fijo para las tres funciones.)
Este es computacionalmente universal, ya que cualquier máquina de Turing puede ser simulada por recorrer en algunos finito composición $F$ de los casos de estas tres funciones con algún valor inicial de $n$. La itera $F^k(n)$ simular la evolución de la configuración de la máquina, llegando a $0$ fib de la máquina, finalmente, se detiene.
Es indecidible si la itera $F^k(2)$ de una composición arbitraria, finalmente, alcanzar la $0$.
PD: Cualquier composición $F$ que simula un universal de la máquina de Turing (y no será infinitamente muchos de estos) sirve como una sola función universal de la computación (cf sola-combinador de bases para lambda términos).
Aquí está el binario original versión de la cadena, en la que todas las funciones de mapa de $\tt\{0,1\}^* \to \{0,1\}^*$:
$$\begin{align}
g_0(s) & = \text{if }s \text{ begins with }\mathtt{1}\text{ then append } \mathtt{0}\text{ to }s\\
g_1(s) & = \text{if }s \text{ begins with }\mathtt{1}\text{ then append } \mathtt{1}\text{ to }s\\
g_2(s) & = \text{if }s \text{ is not empty then delete the beginning element of } s
\end{align}$$
Ahora cualquier máquina de Turing puede ser simulada por algunos finito composición $G$ de los casos de estas tres funciones, de tal manera que la recorre $G^k(n)$ simular la evolución de la configuración de la máquina, llegando a $\epsilon$ (cadena vacía) iff la máquina finalmente se detiene.
Es indecidible si la itera $G^k(\mathtt{1})$ de una composición arbitraria, finalmente, alcanzar la $\epsilon$.
