停止性

日本語活用形辞書

停止性

読み方：ちょうじせい

名詞「停止」に、接尾辞「性」がついたもの。

» 「停止」の意味を調べる

日本語活用形辞書はプログラムで機械的に活用形や説明を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。

ウィキペディア小見出し辞書

停止性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 01:04 UTC 版)

「アルゴリズム」の記事における「停止性」の解説

「計算可能性理論」も参照 アルゴリズムは最終的に必ず停止しなければならないとする定義もある。というより形式的で厳密な議論では停止するものだけがアルゴリズムである（チャーチ＝チューリングのテーゼも参照）。 そのため、そうでないものと呼び分ける必要があることもあり、クリーネは停止性のあるアルゴリズムを「decision procedure for the question」「decision method for the question」「algorithm for the question」とした。停止しない可能性のある手続きについては、クヌースは「computational method」と呼び、クリーネは「calculation procedure」「algorithm」と呼んでいる。 ミンスキーは、（特定の状態から開始された）アルゴリズムの停止性について次のように述べている。 しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。 アラン・チューリングが停止性問題として提起したとおり、任意のプロシージャと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズムは存在しない（この前半を「任意のアルゴリズムと初期状態が」としてはいけない。この記事の他の部分では完全に混用されているが、この文の後半の「アルゴリズムは」という表現は、必ず停止するもののみを指してそう言っているのだから。せめて1文の中では混用はまずい）。 不完全な（あるいは間違った）アルゴリズムは、次のいずれかの結果となる。 停止しない。 解の範囲を逸脱した値を返して停止する。 誤った解を返して停止する。 解を返さずに停止する。 これらの組合せ。 クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案した。また、結果が真理値である場合についてクリーネは第三の論理記号「 u 」を使うことも提案している。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとした。誤った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決される。 通常、これ（アルゴリズムがμ再帰関数を正しく定義しているかという問題）には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。