1.16

设 $f: \mathbb{N}\rightarrow \mathbb{N}$ 满足 $f(0)=0$ $f(1) = 1$ $f(2) = 2^2,$ $f(3) = 3^{3^3}$ $\cdots \cdots$ $f(n) = n^{.^{.^{.^n}}} (\text{the number of } n \text{ is } n)$ 证明：$f \in \mathcal{PRF} - \mathcal{EF}$

证明

令 $g(m,n) = n^{.^{.^{.^n}}}$，具有 $m$ 个 $n$ 的形式，

$\left\{\begin{array}{ll} g(0, n) = N^2n \\g(m+1, n) = n^{g(m,n)}\end{array}\right.$，从而 $f(n) = g(n, n)$

$\because g \in \mathcal{PRF}$

$\therefore f \in \mathcal{PRF}$

以下证 $f \notin \mathcal{EF}$

从而 $\exists k ~\forall n, f(n) < 2^{.^{.^{.^{2^n}}}} \} k$ 个 2，取 $n = k+2$，从而

$(k+2)^{.^{.^{.^{(k+2)}}}} \}k+2$ 个 $< 2^{.^{.^{.^{2^{(k+2)}}}}} \}k$ 个 2，矛盾。