空にカードを放り投げて....

空にカードを放り投げて、バラバラになった結果が、「ソートされているかどうか」をチェックする

というのは、一応ソートのアルゴリズムにならないわけではないです。つまり、すべての順列を作成し、最初から最後までソートされているものを選択する...というアルゴリズムだって、「ソートのアルゴリズム」として間違った解答を返すものではありません.....ただし、極めて邪悪なので　Jargon File によると「ボゴソート」という名前がちゃんとついていたりします。

典型的な邪悪で恐るべきアルゴリズム（これと対照的に bubble sort は単に悪いアルゴリズムの総称）。

勿論私も「ボゴソートを使え！」などと邪悪なことを言うつもりはないのですが、前回の「パーミュテーション検定」の話とも関わって、考えることです。

勿論ボゴソートは無意味なアルゴリズムです。しかし、もし、あなたが1000台のコンピュータを同時に動かすことができ、あらかじめ長さ n のすべての順列のリストが用意されているのならば、その計算量は O(n) になってしまいます。これはクィックソートを使ったとしても、どうせ O(n log n) になってしまうのですから、実は「優れた」アルゴリズムだ、というサカサマの結論が得られる....というあたりに面白みを感じないでしょうか？

マルチスレッドモデルで、平行プログラミングを行う...というのは、まだまだそれほど一般的な話とまではいかないでしょう。どっちか言えば、平行性を持たせることで起きる障害を、なるべく少なくする、という「守り」の視点でマルチスレッドプログラミングを勉強することの方がずっと多いわけです。そうではなくて、

本質的に並行的なアルゴリズムを使い、そのメリットを充分に味わいたい！

というような「攻め」の視点が、ようやく現実的なリソースの問題として捉えても良いようになってきた.....のかもしれません。もし、1000台のコンピュータで同時に実行できるのならば、前回紹介したパーミュテーション検定はあらゆる検定に勝る検定力を持ち、かつそのどれよりも高速、ということになることだってあるわけです。私は「非決定性チューリング機械」という視点からの発想、というものを今後少し考慮に入れてもいいのかも....という感覚を持ち出したわけですね。

フツーのプログラムに使われるアルゴリズムは、決定的なアルゴリズムです。具体的なプログラムとして、

内部でちょっとしたシミュレーションみたいなことをして、比較したいくつかの結果のうち最高のものをとりあえず「解」として返す

というようなやり方をすることはほとんどありません（それでも TeX のレイアウトアルゴリズムでこういうのやってる...という話がありますが）。しかし、今後こういう手法も一般にアリ、になるのでは...などと空想するのはちょいと楽しいことです。

まあ、ここらへん、いわゆる「非決定性アルゴリズム」というタイプのアルゴリズムです。「必ず正解を返すアルゴリズムの計算量が多すぎるために、『必ず正解』ではないけども、間違う確率が極めて小さい高速なアルゴリズムを使う」というと、「素数判定アルゴリズム」はそういうタイプのもので、これは皆さんも日常的に使っている（ＲＳＡ公開鍵暗号とかで活躍しますよね）わけです。ですから、必ずしも「わけのわからない神秘のアルゴリズム」というわけでもないでしょう。

そういう「非決定性」の入り口に、実は Erlang のプロセスモデルは役に立つ、のかも。「ボゴソートが邪悪でない世界」というのもあるのかもしれませんよ！