原始再帰的定義と関数の値

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $h:{\mathbb{N}}^3\to \mathbb{N}$ を
$$g(y)=y+1,h(n,z,y)=z+y+3$$
で定め、関数 $f:{\mathbb{N}}^2\to \mathbb{N}$ を原始再帰
$$f(0,y)=g(y),f(n+1,y)=h(n,f(n,y),y)(n,y\in \mathbb{N})$$
で定める。$f(n,y)$ を $n,y$ の式で表せ。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。$\mathbb{N}$ 上の関数を次の原始再帰で順に定める。

$(1)$ 符号関数 $\mathrm{sg}$：$\mathrm{sg}(0)=0,\mathrm{sg}(n+1)=1$

$(2)$ 打ち切り差 $x\dot{-}y$：$x\dot{-}0=x,x\dot{-}(y+1)=\mathrm{pd}(x\dot{-}y)$。ただし $\mathrm{pd}(0)=0,\mathrm{pd}(n+1)=n$ とする。

$(3)$ 関数 $r$：$r(0)=0,r(n+1)=(r(n)+1)\cdot \mathrm{sg}(2\dot{-}r(n))$

$(4)$ 関数 $f$：$f(0)=0,f(n+1)=f(n)+(n+1)\cdot \mathrm{sg}(r(n+1))$

このとき $f(30)$ の値を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $j\in \mathbb{N}$ に対し、$g^{(j)}$ を $g$ の $j$ 回合成（$g^{(0)}$ は恒等写像、$g^{(j+1)}=g\circ g^{(j)}$）とする。

関数の列 $f_k:\mathbb{N}\to \mathbb{N}$（$k=0,1,2,\dots$）を次で定める（アッカーマン関数と同じ増大度をもつ階層の一種である）。
$$f_0(n)=n+1,f_{k+1}(n)=f_k^{(n+1)}(n)(k,n\in \mathbb{N}).$$
このとき、$f_3(1)$ の値を求めよ。

自然数は $0$ を含むものとし、$\mathbb{N}=\{0,1,2,\dots \}$ とする。$p_i$ で $i$ 番目の素数を表す（$p_0=2,p_1=3,p_2=5,\dots$）。$n\ge 1$ と $i\in \mathbb{N}$ に対し、$(n{)}_i$ を「$p_i^e\mid n$ となる最大の $e\in \mathbb{N}$」と定め、$(0{)}_i=0$ とする。

長さ $k\ge 0$ の有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$┌a_0,\dots ,a_{k-1}┐=\prod _{i<k}{p}_i^{a_i+1}$$
と定める（空列のゲーデル数は $1$）。関数 $F:\mathbb{N}\to \mathbb{N}$ を、$n$ がある有限列 $(a_0,\dots ,a_{k-1})$ のゲーデル数であるとき $F(n)={\sum }_{i<k}{a}_i$、そうでないとき $F(n)=0$ と定める。

$F$ が原始再帰関数であることを証明せよ。

ただし、次の事実は用いてよい。
- $x+y$, $x\cdot y$, $x\dot{-}y$（$x\ge y$ なら $x-y$、そうでなければ $0$）、$x\mapsto p_x$、$(n,i)\mapsto (n{)}_i$ は原始再帰関数であり、述語 $x\mid y$ と $x<y$ は原始再帰的である。
- 原始再帰関数・原始再帰的述語の全体は、合成、原始再帰、論理結合子 $\neg ,\wedge ,\vee ,\to$、有界量化 $\forall i<m$, $\exists i<m$（$m$ は原始再帰関数の値）で閉じている。また、述語 $P$ が原始再帰的であることは、その特性関数 ${\chi }_P$（$P$ が成り立てば $1$、そうでなければ $0$）が原始再帰関数であることと定義する。
- 素因数分解の一意性。

この問題では自然数 $\mathbb{N}$ は $0$ を含むものとする。$p_0=2,p_1=3,p_2=5,p_3=7,p_4=11,p_5=13,\dots$ を小さい順に並べた素数とする（$p_i$ は $0$ 番目から数えて $i$ 番目の素数）。

正の整数 $c$ と $i\in \mathbb{N}$ に対し、$c$ を素因数分解したときの $p_i$ の指数を $e_i(c)$ とする（$p_i$ が $c$ を割り切らなければ $e_i(c)=0$）。さらに
$$(c{)}_i=\max (e_i(c)-1,0)$$
と定める。例えば $c=2^2\cdot 3^3$ のとき $e_0(c)=2,e_1(c)=3,e_2(c)=0$ なので $(c{)}_0=1,(c{)}_1=2,(c{)}_2=0$ である。

関数 $g:\mathbb{N}\times {\mathbb{Z}}_{>0}\to \mathbb{N}$ を、正の整数 $c$ に対して
$$g(0,c)=1,g(m,c)=(c{)}_{\lfloor m/2\rfloor }+(c{)}_{m-1}(m\ge 1)$$
で定める（右辺の 2 つの項はどちらも上で定めた $(c{)}_i$ の値の和であり、$g$ を再帰的に使うものではない）。さらに関数 $F:\mathbb{N}\to {\mathbb{Z}}_{>0}$ を
$$F(0)=1,F(n+1)=F(n)\cdot p_n^{g(n,F(n))+1}(n\in \mathbb{N})$$
で定める。例えば $F(1)=1\cdot p_0^{g(0,1)+1}=2^2$ である。

このとき、$F(6)$ を素因数分解したときの素数 $13$ の指数 $e_5(F(6))$ を求めよ。