アルゴリズム
アルゴリズムは最終的に必ず停止しなければならないとする定義もある。というより形式的で厳密な議論では停止するものだけがアルゴリズムである(チャーチ=チューリングのテーゼも参照)。
そのため、そうでないものと呼び分ける必要があることもあり、クリーネは停止性のあるアルゴリズムを「decision procedure for the question」「decision method for the question」「algorithm for the question」とした。停止しない可能性のある手続きについては、クヌースは「computational method」と呼び、クリーネは「calculation procedure」「algorithm」と呼んでいる。
ミンスキーは、(特定の状態から開始された)アルゴリズムの停止性について次のように述べている。
アラン・チューリングが停止性問題として提起したとおり、任意のプロシージャと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズムは存在しない(この前半を「任意のアルゴリズムと初期状態が」としてはいけない。