これはen:User_blog:P進大好きbot/How_to_Create_a_Recursive_Notationの和訳です。


このページはthe common failuresを繰り返さないようにしつつ、計算可能な表記を定義する方法の簡易的なガイドラインです。私(訳注: p進大好きbot)はこのブログポストをあなたの表記の問題を説明するために使いますが、もしこのブログポストのある部分について理解できなかった場合、ただ「OK、分かったよ」と返すのではなく、ぜひ私(訳注: p進大好きbot)に質問してください。


一般的なこと

計算可能な表記を定義する方法を学ぶ前に、まずは定数や(もしかしたら計算不可能な)関数、(もしかしたら計算不可能な)関係などの対象を新たに定義する方法を学ぶ必要があります。

  1. 関数や関係に対しては、定義域を定義する。
  2. は次の対象のみを使って定義する:
    1. 関数や関係の入力として与えられた対象。
    2. 既に定義された対象もしくは同時に定義された対象。
    3. 量化された対象。

ここで、定義域とは入力の組が動く正確な範囲のことです。また、数列や関数の族の添え字は入力として数えられます。例えば、数列は添字に関する関数であるとみなされます。定義域を明確にする方法については、よくある失敗集の"Lack of the Clarification of the Domain" sectionを参照してください。

厳密に上記の必須条件に従いつつ、考えられる全てのケースに対して適用できる正確な定義を明示的に書き下すということをしない限りは、その新たな対象はただill-definedとなります。

  • 有限個のたくさんの例をリストアップする?
  • 直感ベースの説明?
  • 省略記号(…)の使用による曖昧さ?
  • 「それは同じような方法で展開する」とか「このパターンを繰り返す」?
  • 未定義な対象を含む説明?
  • 一意でない、未量化の値を用いた計算?
  • 複数の展開ルールが、一つの標準的な式に対して一意でない方法で適用可能?

もし新たな対象を正確な方法で定義したならば、これらのような追加の説明は他の人にとって理解する手助けになるかもしれません。しかしながら、そうでないならば、正確な定義のない新たな対象に対するこれらのような類いの説明は無意味です。

今一度この重要な必須条件を繰り返します。いかなるケースにも適用可能な、正確な計算ルールを明確にしなければなりません。 定義域を明確にしているか、そして定義域内のいかなる入力に対してもルールが適用可能か、もう一度チェックしてみましょう。

もし定義域を定義しなかった場合、それが明確に関数型論理式として機能するものでない限りill-definedとなりますし、関数型論理式として扱う場合は直接量化することができません。関数型論理式周りの形式論理学に馴染みがないのであれば関数型論理式を適切に扱うこともきっとできないと思いますので、関数の定義域は明確にしましょう。

関数自身をその関数の定義域の定義に用いるのは、典型的な circular logic(循環論法)です。表記からill-defined性を取り除く方法の詳細な提案については、 こちらを参照してください。

部分特殊化

部分特殊化は関数を定義する一つの方法です。部分特殊化はルールの場合分けが完全かつ重複していない場合にのみ機能します。よくある失敗集の"Incomplete Partial Specialisation" section"Overlapping Partial Specialisation" sectionも合わせて参照してください。

例えば、\(S\)を文字\(X\)と\(+\)と\(\times\)のみからなる文字列の集合とします。次の例は初心者にありがちな、部分特殊化を使った関数\(f \colon S \to \mathbb{N}\)の定義です:

  1. \(f(X) = 0\).
  2. \(f(A+B) = f(A)^{f(B)}\).
  3. \(f(A+X) = f(A) \uparrow \uparrow \uparrow 3\).
  4. \(f(A \times B) = f(A + f(B))\).
  5. \(f(A \times X) = f(A + \cdots f(A) \cdots)\).

この定義にはとてもたくさんの問題があります。

  1. 変数\(A\)と\(B\)が未定義かつ未量化なので、読み手にはそれらが自然数なのか、それとも\(S\)に属する項なのか、はたまた\(S\)に属する項の部分文字列なのか、全く見当がつかない状態となってしまいます。よくある失敗集の"Lack of the Quantification of Variables" sectionも参照してください。
  2. 部分特殊化ルール\(f(A+B) = f(A)^{f(B)}\)は機能しません。なぜなら\((A,B)\)の組は\(A+B\)からは一意的に決定できないからです。(例として、このルールを\(f(X+X+X)\)に適用したいとします。そうすると、\(A\)と\(B\)の取り方によって\((A,B) = (X+X,X)\)と\((A,B) = (X,X+X)\)の、2通りの解釈が発生します。このとき、読み手は書き手がどちらの解釈を取ることを意図しているのか分からないため、計算を進めることができなくなってしまいます。よくある失敗集の "Non-Unique Division into Substrings" sectionも参照してください。
  3. 部分特殊化ルール\(f(A+X) = f(A) \uparrow \uparrow \uparrow 3\)は機能しません。なぜならこのルールは2番目のルールと重複しているからです。例えば、2番目とこの3番目のルールは\(f(X+X)\)に対して両方とも適用可能です。このとき、読み手は書き手がどちらのルールを適用することを意図しているのか分からないため、計算を進めることができなくなってしまいます。
  4. 部分特殊化ルール\(f(A \times B) = f(A + f(B))\)は次のような理由で機能しません:
    1. 部分文字列への一意的でない分割を用いています。例えば、\(f(X \times X \times X)\)は\((A,B) = (X \times X,X)\)と\((A,B) = (X,X \times X)\)の2通りの解釈が可能です。
    2. 他のルールと重複してます。例えば、\(f(X \times X + X)\)はこの4番目のルールの他に1、2、3番目のルールがそれぞれ適用可能です。初心者にありがちなのが、「でも、普通\(\times\)の部分を最初に計算にするよね!」みたいなことを言ってしまうことです。文字列としての\(\times\)と何らかの未定義な演算子\(\times\)とを混同してしまっていますし、何より\(A\)と\(B\)を\((A,B) = (X \times X,X)\)と解釈できてしまうこと、そしてこの解釈の場合ルール3がまだ適用可能なことを忘れてしまっています。そもそも文字列というのはその定義通りただの文字列に過ぎず、文字列への「ルールの適用」に対する「順序」とか「結合法則」とかは持ち合わせていませんし、勝手に備わるものでもありません。
    3. \(f(A + f(B))\)がill-definedです。\(f(B)\)の値は自然数ですから、文字列\(A\)と\(+\)と\(f(B)\)の連結によって得られる文字列の項\(A + f(B)\)は\(S\)に属していません。もし\(+\)が\(S\)に属する項と自然数のどちらにも適用可能な演算子であることを意図しているのであれば、この演算子はただ未定義なものとなります。なぜなら、上記の定義は\(+\)が\(S\)に属する項と自然数の、どちらにも適用可能なようには定義されていないからです。つまるところ、いかに合理的な解釈を行ったとしても、\(f(A + f(B))\)はill-definedなのです。
  5. 部分特殊化ルール\(f(A \times X) = f(A + \cdots f(A) \cdots)\)は機能しません。上記の問題をきちんと理解できていれば、これがたくさんのエラーを含んでいることは明らかに分かるでしょう。

初心者がたくさん部分特殊化を用いた定義の仕方を好みがちな一方で、初心者にとって完全かつ重複のない部分特殊化のルールを考えることは大抵難しいものです。実は、入力された変数の場合分けを行うことで、部分特殊化が引き起こす問題をかなり簡単に解決することができます。例えば集合\(T\)があったとして、いかなる\(t \in T\)に対しても\(f(t)\)を定義したいとします。定義を、場合分けを使って次のように書くと良いでしょう:

  1. もし\(t\)が性質\(P\)を満たすならば、\(f(t) = \cdots\)である。
  2. もし\(t\)が性質\(P\)を満たさず、性質\(Q\)を満たすならば、\(f(t) = \cdots\)である。
  3. もし\(t\)が性質\(P\)と\(Q\)を満たさず、性質\(R\)を満たすならば、\(f(t) = \cdots\)である。
  4. もし\(t\)が性質\(P\)、\(Q\)、\(R\)のいずれもを満たさないならば、\(f(t) = \cdots\)である。

このような定義の書き方の場合、場合分けが完全かつ重複していないのが明らかに分かるでしょう。

例えば、部分特殊化ルール\(f(A+B) = \cdots\)を適用する代わりに、「もし\(t = A+B\)かつ、\(B\)が\(+\)を含まないかつ\(X\)と一致しないを満たす\((A,B) \in S^2\)が存在するならば、\(f(t) = \cdots\)である。」と書くこともできます。つまり、入力\(t\)の状態によって場合分けを考えることができ、(f(t)\)の値をその状態の情報を元に定めることもできます。

もう一度、初心者にありがちな場合分け「もし\(t = A+B\)ならば、\(f(t) = f(A)^{f(B)}\)である。」は機能しないということを注意しておきます。単に部分特殊化ルールを場合分けに置き換えるのみでは、問題を解決できたとは言えません。なぜなら、\(A\)と\(B\)の定義が不明など諸々の問題がまだ残っているからです。また、もし\((A,B)\)の存在性だけでなく\((A,B)\)の組そのものを扱いたい場合は、\(A\)と\(B\)を入力\(t\)や既に定義されている対象のみを用いて適切に定義する必要があります。場合分けを用いる場合、部分特殊化と違って入力\(t\)に言及できるため、\((A,B)\)を特徴づけるのがかなり簡単になります。これは場合分けを用いることの1つのメリットです。

場合分けを行うことのメリットは他にもたくさんあります。未定義かつ未量化な対象が発生している部分を簡単に見つけられます。不完全な場合分けや場合分けの重複を簡単に見つけることができます。たいていの場合、ルールがより簡単に書けるようになるでしょう。その一方で、部分特殊化は定義者がバグを見つけることを妨げてしまいます。なぜなら、定義者はしばしばルールは明らかに機能すると思い込んでしまうからです。部分特殊化の不完全さや重複による問題が指摘されたときでさえ、定義者は「いや、私が正しいよ。あなたが私の書き方についてこれてないだけ。」と言う傾向にあります。なんでこんなことになるんでしょう?

定義者は\(t\)を入力として用意として用意していないため、彼らにとって問題を正確に理解することが困難になります。例えば、\(A\)と\(B\)が\(A+B\)からは一意的に特徴づけられないと指摘すると、彼らは腹を立てて「最初の文字と最後の文字を見てよ!!\(A\)と\(B\)が見つけられるよね!?」みたいなことを言います。そこで、同じ問題を私達が入力値として変数\(t\)を導入して指摘すると、彼らは今度は混乱して「定義に\(t\)なんか使ってませんよね!!これは私の問題じゃなくて、あなたが勝手に変数\(t\)を導入して勝手に間違った解釈をしたことによる問題ですよね!!」みたいなことを言います。

話が理解できましたか?私が思うに、あなたはこんなミスは犯さないと信じていることでしょう。しかしながら、もし部分特殊化が起こす問題を知らなければ、きっとこの手のミスを犯していたことでしょう。これは指摘されるまでは簡単には気づけない、難しい問題なのです。 とにかく、あなたが部分特殊化の使用を避ける上記の提案について、その合理性を理解してくれたら幸いです。もちろん、部分特殊化を使って定義を完璧に書けるなら、使っても構いません。しかし私(訳注: p進大好きbot)の経験上、部分特殊化を好み、問題が指摘されても定義は完璧だと主張する人々は、いつもなんらかのミスを犯しています。問題を理解した後でさえ、彼らは「問題を簡潔に、単純明快でクールな例で説明すべき。変数とかうざったい記号とか使わないでよね。」のようなことを言いがちです。このガイドラインは、私(訳注: p進大好きbot)の、初心者による同じようなエラーを指摘する労力を低減するために書かれました。エラーを指摘してくれる人に、定義を書いた人よりもたくさんの時間をかけて、そのような洗練された小学生にもわかるような例を毎回作る義務があると思いますか?覚えていてほしいのは、それはあなたのやるべきことであって、他の初心者と違って部分特殊化を使ってもエラーなしに関数を定義できるという、あなたの過剰な自信のせいでそうしなければならなくなっているということです。もし何か理解できないことがあれば、自分が絶対に正しいと突っぱねるのではなく人に聞くということをしてください。どうか他の人に、その人が巨大数論に割ける時間の全てを毎回あなたのために使わせようとさせないでください。そうなる前に、問題を理解するために自分の時間を使うようにしてください。


計算可能な表記

以上の事柄を理解できていれば、やるべきことはとてもシンプルです。

  1. 表記に使いたい記号全体の可算集合\(\Sigma\)を明確にする。
  2. 表記として許容する文字列全体の集合\(OT\)を、\(\Sigma\)の有限な長さの文字列全体の集合\(\Sigma^*\)の部分集合として定義する。
  3. もし\(OT\)の再帰性が\(\Sigma\)の自然な数え上げによって明らかにならない場合は、いかなる\(t \in \Sigma^*\)に対しても\(t \in OT\)か否かを判定できる正確なアルゴリズムを明確にする。
  4. \(OT\)の構造を定義する。
    1. もし順序数表記を定義したいなら、\(OT\)上の整列順序\(<\)を定義し、いかなる \((s,t) \in OT^2\)に対しても\(s < t\)か否かを判定できる正確なアルゴリズムを明確にする。
    2. もし再帰的な基本列系を定義したいなら、計算可能な展開ルールの集合を正確にただ1つのルールが \(t \in OT\)に対して適用可能なように定義する。
    3. もし計算可能写像\(f \colon OT \times \mathbb{N} \to \mathbb{N}\)を定義したいなら、いかなる \((t,n) \in OT \times \mathbb{N}\)に対しても\(f(t,n)\)を計算するためのアルゴリズムを明確にする。

相互再帰であることを明示すれば、\(OT\)とその構造は同時に定義することができます。この場合は、相互再帰と循環論法を混同しないように注意してください。

アルゴリズムにおいては、無限順序数のような集合論的な対象を使うことが許されていません。というのも、チューリングマシンの入力と出力は有限な数であると定義されており、有限の数や文字列に対するチューリング完全な計算モデルで模倣可能な操作しか扱ってはならないからです。初心者は、巨大数論者が順序数そのものとその表現式、つまり順序数を表すために用いている文字列とを混同しがちなこと、そして無限順序数が登場してしまうような集合論的な操作を書いて「これがアルゴリズムだ!」と述べてしまう傾向にあることに、特に気を付けなければなりません。もちろん順序数は文字列なんかではありませんし、無限順序数を直接扱う集合論的な操作は当然有限な数や文字列に対する操作とはみなせません。

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