計算理論入門: 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}} - このことから
{\mathcal{E}^n \subset PR} {\bigcup_n \mathcal{E}^n \subset PR} - さらにすべての原始再帰的関数がいずれかの階層に属することも示される:
{\bigcup_n \mathcal{E}^n = PR}
余談
原始再帰の深さは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.
Discussion