アカウント名:
パスワード:
末尾呼び出しの最適化が仕様で保証された言語以外でループ代わりに使うと、あっという間にスタックを使い切る。(再帰的定義で繰り返しを表す発想の起源である)数学ではスタックの深さは無限だから問題にならないだろうけど(ただし停止することの証明が必要)。
数学的帰納法は停止しないよね!…するのか?どっちだろ。
たかだかω回で停止する。(数学的にはそういうのは「停止する」うちに入る)
・A(0)が成り立つかどうかを判定する関数・A(n)→A(n+1)が成り立つかどうかを判定する関数が与えられたとき、与えられた自然数nに対してA(n)が成り立つかどうか判定するプログラムを再帰で書ける(スタックの深さが無限なら)。そのプログラムとnを万能チューリング機械に与えて実行したら、nがどんな自然数でも必ず有限時間内に停止するので、停止する。逆に停止しない可能性があるなら、証明として認められない。
します。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「毎々お世話になっております。仕様書を頂きたく。」「拝承」 -- ある会社の日常
技術的な問題がある (スコア:1)
末尾呼び出しの最適化が仕様で保証された言語以外でループ代わりに使うと、あっという間にスタックを使い切る。(再帰的定義で繰り返しを表す発想の起源である)数学ではスタックの深さは無限だから問題にならないだろうけど(ただし停止することの証明が必要)。
Re:技術的な問題がある (スコア:0)
数学的帰納法は停止しないよね!…するのか?どっちだろ。
Re:技術的な問題がある (スコア:1)
たかだかω回で停止する。(数学的にはそういうのは「停止する」うちに入る)
Re: (スコア:0)
・A(0)が成り立つかどうかを判定する関数
・A(n)→A(n+1)が成り立つかどうかを判定する関数
が与えられたとき、与えられた自然数nに対してA(n)が成り立つかどうか判定するプログラムを再帰で書ける(スタックの深さが無限なら)。そのプログラムとnを万能チューリング機械に与えて実行したら、nがどんな自然数でも必ず有限時間内に停止するので、停止する。
逆に停止しない可能性があるなら、証明として認められない。
Re: (スコア:0)
します。