グジェゴルチク数列 (Grzegorczyk sequence) とは,新井[1]で定義された数列でペアノ算術から停止性が証明できないことが知られている.

定義

以下のとき,そうでないときを表すものとする. を添字が有限な急増加関数とし,[注 1]とする.このとき自然数の底による-表現 (-representation) はに対する帰納法で定義される.

  1. のとき-表現はそのものである.
  2. とする.を満たす最小のものとし,を満たす最大のものとする.
    1. のとき-表現である.
    2. のとき,とし,を満たす最小のものとする.
      1. のとき,-表現である.
      2. のとき,を底とする,-表現とするとき,を底とする-表現である.

ここで-表現がであるというのは,と表されるということである.これを対応する自然数という.

を底とする-表現をとしたとき,のとき,が表現する自然数を表すものとし,のときとする[注 2]

このとき,自然数に対し,グジェゴルチク数列 (Grzegorczyk sequence) ,は以下のように定義される.

  1. \(\begin{align*}z_{k+1}=\begin{cases}z_k\dot{-}1 & \text{if $z_k<2+k$}\\ z_k[2+k:=3+k]\dot{-}1 & \text{otherwise}\end{cases}\end{align*}\).

性質

グッドスタイン数列と同様に,グジェゴルチク数列の停止性,すなわちは標準モデルで真であるが,ペアノ算術で証明できないことが知られている.しかし新井の証明からはのスコーレム関数,すなわち,停止するまでに要するステップ数がペアノ算術の可証全域関数を支配するからペアノ算術で証明できない,という手法ではないためと同じくらいの増大度を持つかは分かっていない.しかし具体的な値を試してみるに,急増大する関数であることが分かる.

遺伝的グジェゴルチク数列

自然数に対してを底とする.完全-表現 (total -representation)は-表現の要素も-表現で表し,その要素も表し……,のように再帰的に定義される.このときを,の完全-表現,に対しを表すものとし,グジェゴルチク数列の定義を上の完全-表現を用いたものを遺伝的グジェゴルチク数列 (hereditary Grzegorczyk sequence) という.遺伝的グジェゴルチク数列の停止性の証明論的強さは未解決である,特にで示せるかどうかも分かっていない.

解析

とする.すなわちから始まるグジェゴルチク数列がになるような最小のである.

Naruyokoとしたときに対してであることを示した[2]

Koteitan-標準形を求めるプログラムを作成している[3]

脚注

  1. なお原論文ではこれをグジェゴルチク関数 (Grzegorczyk function) と言っている.グジェゴルチク階層によると思う.
  2. 原論文ではの場合しか書かれていないが,それでは再帰が上手くいかない.この記事ではの場合,恒等写像としている.

出典

特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。