関数f:\Sigma^\ast\rightarrow\Sigma^\astのこと

定義

多項式時間チューリングマシンMが存在して、

任意の入力u\in \Sigma^\astで動作を開始し、テープにf(u)だけを設定して停止するならば、

fは多項式時間計算可能関数である

ざっくり言えば、

多項式時間チューリングマシンM、を計算する関数のこと

ただのTMじゃなくて、多項式時間TMね

Mと同じ計算をする関数のことを、多項式時間計算可能関数と言う