1.20

证明：$Ack(4,n) \in \mathcal{PRF} - \mathcal{EF}$，其中 $Ack(x,y)$ 是 Ackermann 函数。

证明

令 $f(n) = Ack(4,n)$，

$f(0) = Ack(4,0) = Ack(3,1) = f_3(1)=2^{1+3}-3=13$

$f(n+1) = Ack(4, n+1) = Ack(3, A(4,n)) = Ack(3, f(n)) = 2^{f(n)+3}\dot{-}3$

令 $g(n) = f(n)+3$，从而$g(0) = 16 = 2^4$，$g(n+1) = g(n)$

因此，$g(n) = 2^{\cdot^{\cdot^{\cdot^2}}} \left.\right\}n+3$ 个 $2$

从而，$Ack(4,n) = 2^{\cdot^{\cdot^{\cdot^2}}} \dot{-}3 \in \mathcal{PRF}$

又$\because$ $\lim\limits_{n \rightarrow \infty}\frac{2^{\cdot^{\cdot^{\cdot^2}}} \left.\right\}k \text{ 个 }2}{g(n)} = 0$ $\therefore g \notin \mathcal{EF}$，$\therefore f \notin \mathcal{EF}$ 。