Hatena Blog Tags
はてなブログ トップ
帰納的関数
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

帰納的関数

(サイエンス)
【きのうてきかんすう】

自然数から自然数への関数で、具体的に値を計算するアルゴリズムが存在するもの。
λ記法を使って書くと、

  1. 初期関数
    • ゼロ関数:Z = \lambda x[0]
    • 後者関数:S = \lambda x[x+1]
    • 射影関数U_{i}^{n} = \lambda x_1 x_2...x_n [x_i] (1 \leq i \leq n)
  2. 関数の合成
    • f:n変数関数、g_1,...,g_n:m変数関数とする。
    • 合成f(g_1,...,g_n):N^m \rightarrow Nは
    • f(g_1,...,g_n) = \lambda x_1...x_m[f(g_1(x_1,...,x_m),...,g_n(x_1,...,x_m))]
  3. 原始帰納法
    • g:n変数関数、h:n+2変数関数とする。
      • f(x_1,...,x_n,0) = g(x_1,...,x_n)
      • f(x_1,...,x_n,y+1) = h(x_1,...s,x_n,y,f(x_1,...,x_n,y))
    • と再帰的に定義されるf:N^{n+1} \rightarrow Nをg,hから原始帰納法により定義されたという。
  4. 最小化
    • g:n+1変数関数とする。
    • f=\lambda x_1,...,x_n[\min \{y \in N|g(x_1,...,x_n,y)=0\}]
    • m=\min \{y \in N|g(x_1,\ldots,x_n,y)=0\} が存在し、尚且つ任意の y\leq m に対して g(x_1,\ldots,x_n,y)\downarrow のとき、そのときに限り f(x_1,\ldots,x_n)\downarrow
    • によって定義される関数fを、gから最小化により定義されたといい、\mu y.g(x_1,\ldots,x_n,y) と書く。

1,2,3,4を適用して作られた関数を帰納的関数といい、その中で4の適用が無かったものを原始帰納的関数と呼ぶ。
帰納的関数であれば、whileのみを使ったプログラムで計算が可能である。また、原始帰納的関数であれば、loop(for)のみを使ったプログラムで計算が可能である。
全域帰納的だが原始帰納的でない関数としてアッカーマン関数が例としてしばしば挙げられる。

なお条件3を除いた最小化は一般に帰納的ではない。1-変数帰納的関数 f(x) を考える。ここで次のような関数を考えよう：g(N,x)=\begin{cases} &1& &\text{if $x\lt N$}& \\ &f(x)-f(x)& &\text{if $x=N$}& \\ &0& &\text{otherwise}& \end{cases} これは帰納的関数である。条件3を除いた最小化 \mu x.g(N,x) が帰納的関数だと仮定しよう。もし \mu x.g(N,x)\neq N ならばそのときに限り f(N)\uparrow であるから、これは``停止問題の補問題の半決定手続きが存在する"ことを意味する。停止問題は半決定可能であったから、したがって停止問題は決定可能となるが、これは停止問題の決定不可能性と矛盾する。したがって条件3を除いた最小化 \mu x.g(N,x) は帰納的関数ではない。条件3が上の証明を破綻させることを確認しておこう。もし条件3に従えば、f(N)\uparrow ならば \mu x.g(N,x)\uparrow であるからそもそも \mu x.g(N,x)\neq N が停止せず、したがって停止問題の補問題も半決定できない。

具体例

足し算
\rm{add} = \lambda x y [x+y]

  • \rm{add}(x,0) = U_{1}^{1} (x)
  • \rm{add}(x,y+1) = S(U_{3}^{3})(x,y,\rm{add}(x,y))

掛け算
\rm{mult} = \lambda xy[x \cdot y]

  • \rm{mult}(x,0) = Z(x)
  • \rm{mult}(x,y+1) = \rm{add}(U_{3}^{3},U_{1}^{3})(x,y,\rm{mult}(x,y))

*リスト：リスト::数学関連

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
Redundanz•2 か月前

哲学探究を読む（１９）

労働において自分の関わるいくつかの案件が山場を迎えており、哲学書を読むような気分を維持できずにいた。現実的な問題を解くことにエネルギーを投入している間は、そうした「現実」を前提から支えている枠組みに対する懐疑の気持ちは弱まってしまう。かつての自分は、「現実」が目前に迫ってきてもなおその前提を受け入れることができずに社会適応上の問題を引き起こしていたけれど、最近の自分はどうも生きるのがうまくなってしまった。生存することを度外視した精神活動によってのみ達成できる学問的・芸術的・宗教的境地があることが知られており、二兆円の到来が必要とされている。そういえばウィトゲンシュタインはお金に困ったことがある…

ネットで話題

もっと見る

関連ブログ

faain-635•5 か月前

確率論（もう一つの歴史的役割）

判断する予測すると言う行動も「計算」と言ってよいなら、情報圧縮も誤り検出・訂正もまた確率論に多くを負っている。 キーワード：アルゴリズム チョムスキーの句構造文法 ランダムアクセスマシン プログラム内蔵方式ＲＡＭ ヒルベルトのプログラム ゲーデルの不完全性定理 ゲーデル氏等の計算可能関数（帰納的関数・定義可能関数・ポスト正規システム等） 情報源符号化定理・通信路符号化定理 情報エントロピー マルコフ情報源 平均符号長 参考 「チューリングの計算理論入門」 高岡詠子 著 「シャノンの情報理論入門」 高岡詠子 著

手を動かさなくても分かる行間ゼロの大学数学•5 か月前

帰納的関数論 3：自然数論の形式的体系${\cal P}$

自然数論の形式的体系${\cal P}$を定義する。 記号 対象記号：${\mathbf 0}$ 関数記号：$^\prime$ 論理記号：$\neg$、$\lor$、$\all$ 補助記号：$($、$)$ 変数記号：おのおのの型ごとに、それぞれ可算個無限個ずつの変数を用意する。 $1$階のタイプの変数記号：$x_1$、$y_1$、$z_1$、$\cdots$ これは、${\mathbf 0}$を含む自然数全体上の変数を表す記号である。 $2$階のタイプの変数記号：$x_2$、$y_2$、$z_2$、$\cdots$ これは、自然数上で定義された1変数の述語を表す。 …：… $n$階のタイプの変…

手を動かさなくても分かる行間ゼロの大学数学•6 か月前

帰納的関数論 2

(原始)帰納的述語 $P(x_1, \cdots, x_n)$は自然数上で定義された述語とする。${\cal D}$は関数の有限集合とする。 $P$は${\cal D}$-帰納的述語 $:\Leftrightarrow$ $P$の表現関数$\chi_P$は${\cal D}$-帰納的関数 ${\cal D} \equ \phi$の時は、$P$を帰納的述語という。 $P$は${\cal D}$-原始帰納的述語 $:\Leftrightarrow$ $P$の表現関数$\chi_P$は${\cal D}$-原始帰納的関数 ${\cal D} \equ \phi$の時は、$P$を原始帰納的述語という。…

手を動かさなくても分かる行間ゼロの大学数学•7 か月前

帰納的関数論 1

table.truth_table th{ border: solid 1px white; border-bottom: solid 4px white; padding: inherit; } article.my_article div.centering > table.truth_table td{ border:solid 1px white; margin: 2px; } --> 形式的体系とは、(形式主義の立場では)有限の立場とよばれる構成的な方法で証明論を形式化し、さらに証明論の対象である個々の数学的理論をも、同じように形式化したものである。従って、形式的体系における思考対象…

Haskell勉強会•9 か月前

計算モデルとプログラミング

ラムダ計算を分かりやすく説明した本がありました。 「計算モデルとプログラミング」という本です。 計算モデルとプログラミング 作者:猪股 俊光,山田 敬三 発売日: 2019/04/19 メディア: 単行本 本書を参考にして、ラムダ計算の説明方法を学んでみたいと思います。 目次 著者紹介 出版社情報 書評 目次 第1章 計算の世界と計算モデル 1.1 計算の世界 1.2 計算モデル 1.3 計算モデルとプログラミング言語 1.4 アルゴリズムの記法 1.5 数の体系 1.6 自然数上の計算と計算モデル 演習問題 第2章 抽象機械型計算モデル 2.1 機械による計算のモデル化 2.2 順序機械 2…

アイテックインターナショナル•昨年

アルゴリズムとは。

アイテックインターナショナルです。 アルゴリズムとは、人工知能の設計の一番の肝の部分といっても差し支えないでしょう。歴史記録に残る最古のアルゴリズムは、エウクレイデスの原論のものである。その中でも、二つの整数の最大公約数を求めるユークリッドの互除法[1]は、典型的なアルゴリズムとして知られている。 「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー[2]の名前から来ているといわれている。彼がインド数学を紹介した著作『インドの数の計算法』（825年）が、12世紀にチェスターのロバート（あるいはバースのアデラード）によってラテン語に翻訳され、『algo…