From: gotoken@... (GOTO Kentaro)
Date: 1999-04-15T21:40:12+09:00
Subject: [ruby-list:13777] Turing machine (Re: iterator)

ごとけんです

# ruby-math かな?

In message "[ruby-list:13770] Re: iterator"
    on 99/04/15, YANAGAWA Kazuhisa <kjana@os.xaxon.ne.jp> writes:

>「良くプログラミング関係の人が『非決定性』という言葉を間違って使ってい
>る．だってあれは単なるランダム性じゃないか」という理論系の先生の言葉を
>思い出したり．

ランダム性というのはまた難しい概念ですね。どこでも通用する定義は
ないんじゃないかなぁ。

>その講義がオートマトン関連の計算理論についての物だったので，「非決定性」
>といったら「あらかじめ全ての入力が与えられているかのように，選択が必要
>な局面では必ず正しい選択を行う」が「その時点までで与えられている入力か
>らは次の選択がどうなるかわからない」という性質の事だったのですよ．

ぼくが非決定性といったのは nondeterminism ではなく
undecidability (決定不能性)のつもりでした。Turing機械の受理能
力は deterministic でも nondeteministic  でも同じなんだけど、
計算機は物理的な系なので undecidable なキーボード入力なんかを
使って、 uncomputable な関数を実現することができますね。もっ
ともTuring機械には実行時入力やクロックがないからくらべるのが
そもそも変なんですが。

>実際プログラミング系の話で「非決定性」といったら「与えられた入力から次
>の選択が予想できない」という部分しかない場合が多いですね．

そうですね。これはややこしいいい方をすると実行時入力が 
undecidable であるということにほかならないと思います。

まぁとにかく Turing machine とプログラミング言語を並べて議論
するのに無理があるだけでなく、プログラミング言語同士の能力の
違いを科学的に自然に測れるかどうかは疑問に思います。もっとも、
どんなプログラミング言語も僕の任意のお願いを聞いてくれないの
は確かなんですが。好き嫌い以上の物をアピールするならなにか工
学的な観点を導入して比較するべきでしょう。残念ながら僕はまだ 
ruby の良い所を理論的に主張するにはいたっておりませぬ(^^;;;

>> iterator? の alias として given_block? なんてのを用意するのも
>> いいかも知れませんね。
>
>「与えられたブロック」の方が「true」って答えそうな名前ですね．
>block_given?

みなさんおっしゃるように、block_given? のほうがよいですね。

# センスがないぞ > 俺

青山さんの block_call にも賛成です。

-- gotoken