アカウント名:
パスワード:
多分, 有名な停止問題 [nagoya-u.ac.jp]を知らないんでしょう.
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
にわかな奴ほど語りたがる -- あるハッカー
あるなら俺にくれぃ! (スコア:3, おもしろおかしい)
1を聞いて0を知れ!
Re: (スコア:0)
Re: (スコア:0)
Re: (スコア:2, 参考になる)
多分, 有名な停止問題 [nagoya-u.ac.jp]を知らないんでしょう.
Re: (スコア:0)
Re: (スコア:1)
一応マジレスしておくと,言語にチューリングマシンと同等の記述能力を持たせようとすると,そもそもあるプログラムに無限ループ構造があるかを判定するのが無理(停止するかどうかを判定するのに無限の時間がかかる)というのが停止問題のおおざっぱな内容.ちなみに,プログラミング言語にはチューリングマシンと同等の記述能力を持たせるのが普通じゃないかなぁ(ここは自信なし).
Re: (スコア:0)
っていう前提が停止問題での無限ループを判定するのは無理という話ですよね。
つまり、チューリングマシンを前提としている。
すでに純粋関数型言語ではチューリングマシンの前提の一部は崩れている。
有限のリストを実用上必要とするときに無限ループを組むことはあるが、
それは言語仕様の本質とはずれている。
純粋関数型言語をもう少し進化させると、状態変化を伴う無限ループを記述すること自体できないような仕様の進化があり得ないとまでは言えない。
とすれば、無限ループを評価できないのは言語仕様に依存すると言えるでしょう。
Re: (スコア:0)
これは初耳です。もう少し詳しく説明してください。
Re: (スコア:0)
・順次評価
・ループさせながら状態を変化させて解を探索
を持っていない
評価されなければ無限ループには陥らない。
たとえば、循環参照を定義したとしても、それをプリントするまでは無限ループしない。(CやJavaのようなチューリングマシンも)
逆にプリントという副作用を定義するときは有限の限界値を指定しない限り実行できないという仕様にする。
(普通はプログラマが自主的にケアしてしまえば済むなので実用性がないだけ。言語仕様として実装は可能)
# 停止性問題は非決定性チューリングマシンに対してまでは証明されているんだろうか?
Re: (スコア:0)
# 非決定性も決定性でシミュレートできますよ。
Re: (スコア:0)
関数型言語の入門部分をラムダ関数で表現できたからといって、
結局同じと言ってしまうあたり、言語仕様の理解、大丈夫です?
仮に完全にエミュレートできたとしてもそれはチューリングマシンで
関数型言語の仕様を実現するのであって、
その時にはチューリングマシンの持っている特性の一部は関数型言語の仕様の名のもとに制約を受ける。
よってチューリングマシンでの命題が関数型言語でも同値とは言えないよね
Re: (スコア:0)
Re:あるなら俺にくれぃ! (スコア:0)