III.

数学と論理学

論理学や数学基礎論などでアルゴリズムという場合は、有限の時間で確実に答がでて終了する計算規則をさす。そのために、(1)問題や答をふくめて、とりあつかうデータは有限の記号列で記述できる、(2)アルゴリズムを構成している各ステップは機械的に実行でき、有限時間で終了し、計算の結果はただ1つに決定される、(3)アルゴリズムに対してどのような入力があたえられても、有限の時間内に出力して終了する、といった条件を満足していなければならない。つまり、アルゴリズムは不確定の要素をふくんではならない。

問題を解くアルゴリズムが存在するかどうかを計算可能性といい、コンピューターで処理する場合に必要とする時間やハードウェアの資源を、計算の複雑さという。