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)\}
特性関数
code:プログラム
haltPair(y) {
int dummy;
dummy = comp(left(y), right(y));
return(1);
}