At Tue, 14 May 2002 18:55:49 +0900,
Takaaki Tateishi wrote:

> At Tue, 14 May 2002 18:16:06 +0900,
> > >そうかも知れません。Lawvereの不動点定理は写像の性質だけしか
> ...
> > >(Tarskiの)不動点定理があれば済みますね。
> > Tarski のってのは知りませんでした。
> 不動点定理っていろいろあるんですね.他にもあるのでしょうか?

多分もっともよく知られてるのはいわゆる縮小写像の定理でしょう。
距離空間ごとに興味を持たれる縮小写像の定理がありますね。その
中には R^n の non-empty compact subset 全体に Hausdorff 距離
を入れた空間の上での 畑-Hutchinson の定理とか Barnsley の 
Collage 定理があります。これらのフラクタルの定理と Tarski の
不動点定理は無関係ではなくて、むしろよく似ているという林晋さ
んの指摘やその影響を受けた Edalat の仕事は面白いものです。

Susumu Hayashi, 
``Self-similar set as Tarski's fixed points'', 
Publ. Res. Inst. Math. Sci., 21 (1985) 1059-1066

Abbas Edalat, 
``Dynamical Systems, Measures, and Fractals via Domain Theory'', 
Info. and Comp. 120 (1995) 32-48

それから面白いのは Kleene の第二帰納定理です。今風に平たくい
えば自己記述関数(自分自身を出力するプログラム)が存在すること
を述べたものです。ロジックの教科書には大抵載っています。

確か More Programming Pearl だった思いますが、自己記述関数の
作り方として、エラー出力も出力に含めて任意のテキストを反復的
にコンパイラに食わせるといずれ収束するという話がありました。
しかし周期2以上の周期軌道に落ちる場合の方が多いと思います。

ところで、 Bernstein の定理という集合の基数に関する定理があ
りますが、この証明は不動点を構成することで行なうのが簡単で、
実際そういう証明を採用している教科書が多いように思います。

不動点という考え方は計算機科学では僕の知る限りもっぱら意味論
やその基礎である領域理論で基本概念として使われています。昔は 
Plotkin の Domains という講義ノートが広く読まれていたようで
すが、最近入手しやすいのは Abramsky と Jung のチュートリアル
かも。これは確か邦訳されてなんとかハンドブック(失念)に載って
います。

Samson Abramsky, Achim Jung, 
``Domain Theory'', 
Handbook of Logic in Computer Science, vol. 3 (1994)

そういえば、10年くらい前の『情報処理』に「不動点」という特集
がありました。読んではいませんけど。
http://www.ipsj.or.jp/members/Magazine/Jpn/3304/

-- Gotoken