計算可能
computable
計算可能とは、それを計算する計算手順が存在するということ
計算手順にはいくつかの流儀があり、それらの異なる流儀でも計算可能性の概念は全て一致する
『C言語による計算の理論』.icon p.18
自然数上の$ k変数部分関数$ fに対してそれを計算する$ k入力プログラムが存在するとき$ fは計算可能であるといい、存在しないとき$ fは計算不可能であるという $ k入力プログラムを書けたから、「$ fは計算可能です」というのはわかる
が、「$ k入力プログラムを書けなかったので、$ fは計算可能ではありません」といえる(?)のがわからない
計算可能な関数の計算手続きの満たすべき条件
その関数は、任意の大きさの引数を扱えなければならない
その関数の手続きを終了するまでの制限時間はない
その手続きの計算のために使用する有限空間の使用量に制限はない
「計算可能」って数学的に厳密な定義ってないのか？
「それを計算するC言語で記述されたプログラムがある」とか
「それを計算するチューリングマシンがある」みたいな表現になるのか
参考