[雑記]雑記2008年1月5日(土)

2008年1月 6日 01:32 at-akada | 個別ページ | コメント(0) | トラックバック(0)

■ ノンジャンル

いつもブログの下書きを「連想メモ帳」というアプリケーションにメモしているのだけど、今開いたら数日前に2007年のベストについて悩んだあとがあった。

■ 2007年のベスト。

ノンジャンル

論理哲学論考

とかち

百合星人ナオコさん

3つしか思いつかなかったらしい。ひどい組み合わせだ。

■ ●√□

あいかわらず実家にいる。

鏡音リン動画を見ながらゲーデルを読んだりしている。

とりあえず前半の関数はほぼすべてJavaScriptでも(関数を返す関数を書けるような言語なら何でもいい)「書ける」ことがわかった。

以下のようにして段々複雑な関数をつくっていく。

原始再帰関数 - Wikipedia

も参照。

出発点として以下の3つの関数のみを許す

Constant

定数関数。

つねに0を返す関数。

Successor

直後関数。

与えられた数の次の数を返す関数。つまり1を足す関数。

U(n)

射影関数。

n番目の引数を返すだけの関数*1。主に下の合成と一緒に使う。

上記3つの関数はもちろんJavaScriptでも書ける。

ただしU(n)はn個あるので、nを渡して新しい関数を返すような関数Uをつくることで何とかする。

U(2)(3,4,5)
//=> 4

関数をつくる操作として以下の2つのみを認める。

再帰的定義

初期化用の関数と差分を求める関数を渡して新しい関数をつくる。

説明しづらい。

$\phi(0,x_2,...,x_n) = \psi(x_2,...,x_n)$

$\phi(k+1,x_2,...,x_n) = \mu(k,\phi(k,x_2,...,x_n),x_2,...,x_n).$

合成

ある関数の引数を他の関数でフィルターするようにして、新しい関数をつくる。こっちも説明しづらい。

たとえば、

add2 = Successor.compose(Successor)

直後関数(Successor)の引数に直後関数の結果を渡すようにして、新しい関数をつくる。つまりここでは2をプラスする関数をつくっている。

これらの操作は関数を受け取って新しい関数を返すようなJavaScriptの関数として実装する。Compose(Successor,Successor)より、Successor.compose(Successor)の方が見やすいと思うので、composeはFunctionコンストラクタのプロトタイプ関数にする。

(toArrayは自分で適当に実装する)。

function RecursiveDefinition(psi,mu){
    var phi = function(){
        var args = toArray(arguments),
            n = args.shift();
        
        if(n == 0){
            return psi.apply(null,args);
        }
        else if(n > 0){
            return mu.apply(null,
                [   
                    n-1, 
                    phi.apply(null,[n-1].concat(args))
                ].concat(args)
            );
        }
    };
    return phi;
}

Function.prototype.compose = function(/*function list*/){
    var functionList = arguments,
        psi = this;
    var phi = function(){
        var originalArgs = arguments;
        var filetered = [];
        for(var i=0,l=functionList.length;i<l;i++){
            filetered.push(functionList[i].apply(null,originalArgs))
        }
        return psi.apply(null,filetered)
    };
    return phi;
};

原始関数も新しい関数をつくる操作も書ける。そしてゲーデルが書いている関数は(1つを除いて)すべてこれらだけを使ってつくられているので、原理的には(1つ以外)すべてJavaScriptでも書ける。

たとえば2項の足し算をする関数は以下のようになる。

add = RecursiveDefinition(
    U(1),
    Successor.compose(U(2))
)

ゲーデルが自明と言って飛ばしたイコールも意外に難しかった。

subは引き算とし、andFは2項がともに0のときのみ0、それ以外の場合には0を返す関数であるとする(ふつうと逆で0がtrue、1がfalseになってる)。

eqFは2項が等しいときにのみ0を返す。

(つまり A==B <--> A-B==0 かつ B-A==0)

eqF = andF.compose(
        sub.compose(
            U(1),
            U(2)
        ),
        sub.compose(
            U(2),
            U(1)
        )
);

で、最初の方の自明な関数と関数3くらいまで書いてみたんだ。定理4は関数そのものではなくて最小値を求めるような関数をつくるためのアルゴリズムを解説したものなので、それは関数を受け取って関数を返すJavaScriptの関数として書いたんだ。

しかし、13が素数であることの判定に5分くらいかかった...。

無論パフォーマンスなんかゲーデルの知ったことではないのである。

だからゲーデルの関数を逐語訳的にJavaScriptに翻訳すると絶対動かないんだよ。正月を完全にこれに費してしまったよ......。

一応以後の展開を解説しておく。

この論文ではこうやって段々複雑な体系を構築し最終的にはこの関数の体系の中でもう1つ別の体系を動かすことを目指す。

しかる後に、「外の体系」でできることはすべて「中の体系」でもできることを証明し、「中の体系」のなかでさらに「中の体系」を動かすというマッドな展開へと進んでいく。そこからが面白いんだが、まだ全然クリアに把握できていない。外の体系と中の体系が交差する辺りが複雑すぎて、知恵熱が出そうになってきた。

念のため、鏡音リン動画も紹介しておく。まずは定番(？)のロイツマがなかなかよかった。