[雑記]雑記2007年9月28日(金)

■ 新刊とか

わたしがほにゃで発見したことを書く。

• 『論理的原子論の哲学 (ちくま学芸文庫 ラ 4-2)』

バートランド・ラッセル(著), 高村夏輝(訳)

ちくま学芸文庫(筑摩書房)、2007

■ 再帰

「再帰(recursive)」という語の意味を日本語で説明しようと試み、しばらく考えることがある。

これについては今のところ、「先行-後続の関係で結ばれたものの集まりにおいて、先行の要素から後続の要素に向けて同じ操作を繰り返すこと」という暫定的な解答を得ている。

(「操作」という語は最大限広義に解釈するものとする)

まず用法の具体例を示す。

たとえば、ディレクトリを、中にあるディレクトリやファイルごとコピーすることを「リカーシブにコピーする」と言う。これは、最初に一番上のディレクトリをコピーし、次にその中にあるものをすべてコピーし、次に、その中にもしもまたディレクトリがあれば、そのディレクトリに対して同じことを繰り返し、末端の要素にいたるまでその一連の操作をつづけることを言う。

コピー1： D1のコピー
コピー2：=>D2のコピー
コピー3：=>D3のコピー
=>終了

この場合は、ディレクトリのリストに対し、コピーの操作を繰り返している。

また論理学などで見られる語用に、「再帰的定義」というのがある。これは以下のようなものである。

1 原子式は論理式である
2「NOT(論理式)」は論理式である
3「(論理式)OR(論理式)」は論理式である
4 1, 2, 3によって論理式とされるものだけが論理式である

このような定義においては、先行の要素に"AND""OR"を付加することで、次々と新たな論理式を得ることができる。

定義1:P1は論理式である
定義2:=>P2： NOT(P1) は論理式である
定義3:=>P3： (NOT(P))OR(P) は論理式である
...

この場合は、論理式のリストに対し定義の操作が繰り返される。

また反対に、A(n)が論理式であるかどうかを判断するには、まずA(n)が

NOT(...)

(...)OR(...)

の形であるかどうかを判断し、もしもそうであれば、(...)に対し同じことを繰り返せばよい。

また、プログラミングの用語で再帰的な関数というものがある。

これは以下のようなものである

def fact(n)
    if(n==0)
        return 1 
    else
        return n * fact(n-1)
    end
end

ここでfactは自分のなかで再び自分を呼び出している

呼び出し1: fact(3)
呼び出し2:=>3 * fact(2)
呼び出し3:=>2 * fact(1)
呼び出し4:=>1 * fact(0)
呼び出し5:=>fact(0) = 1

この場合は関数の呼び出しが繰り返される。

また再帰的な省略語とか再帰的命名と呼ばれるものもある。

• 再帰的頭字語 - Wikipedia

http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E7%9A%84%E9%A0%AD%E5%AD%97%E8%AA%9E

GNU は"GNU is NOT UNIX"の略とか、VISA は"Visa International Service Association"の略であるとか、そういう略語を指す。

(というか。VISAカード がこの例だったというのははじめて知った)

しかし、私の思うに、これを再帰的頭辞語と呼ぶのはおかしい。

略語の復元は基本的にすべて再帰的な操作であるはずである。

これを説明するために略語のなかに再び略語を含む略語の例を探したが、スーパーファミコンしか思いつかなかった。

(ただし、正確に言えば、スーパーファミコンの正式名称はスーパーファミリーコンピューターではない。思うに、これは任天堂が再帰性に潜む無限の存在に恐怖したためであろう。これでは、あえて無限を恐れないVISAカードに勝てようはずがない)

復元1: SFC は Super Famiconの略
復元2:=>Super Famikonは Super Family Computerの略

ここで再び、Family Computerが何かの略であれば、復元の操作を再び繰り返さなければならない。これは十分に再帰的な操作であり、もしも略語を復元するようなプログラムがあれば、間違いなくそれは再帰を用いて書かれるのではないかと思う。

したがって、GNU が"GNU is NOT UNIX"の略であることを「再帰的」と言って喜んでいるのはまったくおめでたいことである。これはむしろ「反射的」と呼ぶべきだろう。

(前にshimが"GNU"が"GNU is NOT UNIX"の略と聞いて、「プログラマーを一列に並べて銃殺したい」と言っていたのがおもしろかったのでわたしも真似して馬鹿にしてみた。しかし、正直に言うと"GNU is NOT UNIX"という発想はそんなにきらいではない)。

■ 考察:

再帰性に必要なものは何か。順序性である。

人はしばしば入れ子と先行-後続を直観的にわけて考える。しかしこの両者はともに順序性を持つため、再帰的な操作によってもれなくすべての要素を扱うことができる。

では順序性の本質とは何か。

1対多である。

1つの親要素に対して複数の子要素があるのはかまわない。

しかし再帰的に処理される対象は、つねに1つの親要素に対して複数の子要素を持つのでなければならない。

なぜならば、親要素の数が一定でないならば、反復の操作によってすべての要素をつくすことができないからである。その場合は、対象に順序性を持たせる工夫であるとか何とかが必要になる。

以上。