計算可能とは、それを計算する計算手順が存在するということ

計算手順にはいくつかの流儀があり、それらの異なる流儀でも計算可能性の概念は全て一致する

ref チャーチ・チューリングのテーゼ

p.18

自然数上のk変数部分関数fに対してそれを計算するk入力プログラムが存在するときfは計算可能であるといい、存在しないときfは計算不可能であるという

「存在する」とは #??

k入力プログラムを書けたから、「fは計算可能です」というのはわかる

が、「k入力プログラムを書けなかったので、fは計算可能ではありません」といえる(?)のがわからない

計算可能な関数の計算手続きの満たすべき条件

by Herbert B. Enderton

その関数は、任意の大きさの引数を扱えなければならない

その関数の手続きを終了するまでの制限時間はない

その手続きの計算のために使用する有限空間の使用量に制限はない

「計算可能」って数学的に厳密な定義ってないのか？

「それを計算するC言語で記述されたプログラムがある」とか

「それを計算するチューリングマシンがある」みたいな表現になるのか

参考