計算理論入門: Grzegorczyk階層

自己紹介

ごきげんよう、論計舎代表・講師の川井 新です。
本記事では、計算可能関数をご存知の向きにGrzegorczyk階層 (ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy) というものを紹介します。
なお、論計舎は、数理「論」理学と理論「計」算機科学を伝えるオンライン私塾で、三つの柱を重んじて、セッション・コースとクイックコンサル・コース、およびよくよむ会を主に開講し、様々なイベントも行っています。

イントロダクション

本記事では、計算可能関数をご存知の向きにGrzegorczyk階層 (ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy) というものを紹介します。Grzegorczyk階層は、原始再帰的関数をその増加度によって階層分けするものです。

まず原始再帰的関数を復習がてら定義し、その後Grzegorczyk階層を定義します。その後、Grzegorczyk階層の性質を、最後に原始再帰的関数とGrzegorczyk階層の関係を紹介します。

Grzegorczyk階層とは

「グジェゴルチク」と読みます (発音難しいですね) 。これは計算可能性理論に基づく関数の階層で、原始再帰的関数からなり、任意の原始再帰的関数はこの階層のあるレベルに属します。Grzegorczyk階層は、関数の増加度を扱い、階層が高くなればなるほど増加度も大きくなります。

YouTubeでも解説しています。よろしければご覧ください。

原始再帰的関数

まず原始再帰的関数をおさらいしよう。

原始再帰的関数の定義

原始再帰的関数は計算可能である。(cf. [1])

原始再帰的関数の例

• 定数
• 加法: ${x+0=x, x+(y+1) = S(x+y)}$
• 乗法: ${x0=0,   x(y+1)= xy+x}$
• 冪乗: ${x^0 = 1, x^{y+1} = {x^y}x}$

他にも基本的な数論的関数の大半が原始再帰的である。

Grzegorczyk階層の気持ち

Grzegorczyk階層は、原始再帰的関数の増加の度合いを扱ったものである。原始再帰的関数の増加の度合いは、入れ子になった原始再帰の深さによって見積もることができる。
そこで原始再帰の深さによって、原始再帰的関数を分類したい。

Grzegorczyk階層の定義

Grzegorczyk階層の性質

• ${\mathcal{E}^0 \subset \mathcal{E}^1 \subset \mathcal{E}^2 \subset \dots}$
• 実際、${\mathcal{E}^I}$は${B_i}$の閉包であって${B_0 \subset B_1 \subset B_2 \subset \dots}$となるからである。
• しかも、この階層は厳密である: ${\mathcal{E}^0 \subsetneq \mathcal{E}^1 \subsetneq \mathcal{E}^2 \subsetneq \dots}$
• というのも、ハイパー演算子${H_n}$について${H_n \in \mathcal{E}^n}$かつ${H_n \not \in \mathcal{E}^{n-1}}$だからである。
• ${\mathcal{E}^0}$は次を含む: ${x+1, x+2, \dots}$
• ${\mathcal{E}^1}$はすべての加法関数を備える: ${x+y, 4x, \dots}$
• ${\mathcal{E}^2}$はすべての情報関数を備える: ${xy, x^4, \dots}$
• ${\mathcal{E}^3}$はすべての指数関数を備える: ${x^y, 2^{2^{2^x}},\dots}$
• ${\mathcal{E}^4}$はテトレーション関数を備える。

原始再帰的関数との関係

• ${\mathcal{E}^n}$の定義は、再帰が「限定」されていて${(E_k)_{k < n}}$が明示的に導入されていることを除けば、原始再帰的関数のクラスの定義に似ており、実際Grzegorczyk階層は原始再帰の強さを制限しているものと見ることができる。
• このことから${\mathcal{E}^n \subset PR}$であり、したがって${\bigcup_n \mathcal{E}^n \subset PR}$。
• さらにすべての原始再帰的関数がいずれかの階層に属することも示される: ${\bigcup_n \mathcal{E}^n = PR}$ (cf. [4])

余談

原始再帰の深さはloopプログラムにおけるloop深度と密接な関わりがある。

Reference

Amn. 計算理論の魔導書. 2021 link

Andrzej Grzegorczyk. Some classes of recursive functions. 1953

グジェゴルチク階層 wikipedia. link

H Schwichtenberg. He rose. subrecursion. functions and hierarchies. oxford logic guides, no. 9. clarendon press, oxford university press, oxford and new york1984, xiii+ 191 pp. The Journal of Symbolic Logic, Vol. 52, No. 2, pp. 563–565, 1987.