halt
計算不可能
な関数
p(x)
が止まるかどうかの判定をする
$ \mathrm{Halt}(p,x)\iff \mathrm{executable}(p,x)\land(\exist t\in\mathbb{N})\mathrm{HaltBefore}(p,x,t)
定義
halt(p,x)
出力
1:
comp(p,x)
が何らかの解を出力するとき
0:
comp(p,x)
が未定義になるとき