generated at
haltPair
from 『C言語による計算の理論』に出てくる関数一覧

集合
決定不可能
半決定可能
\Sigma_1完全集合の一つ
\mathrm{haltPair}=\{y|(\exist p\in\mathbb{N})(\exist x\in\mathbb{N})\left((y=\mathrm{pair}(p,x))\land(\mathrm{comp}(p,x)\downarrow)\right)\}


特性関数
プログラム
haltPair(y) { int dummy; dummy = comp(left(y), right(y)); return(1); }