計算可能なナンバリング
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/30 14:17 UTC 版)
「ナンバリング (計算可能性理論)」の記事における「計算可能なナンバリング」の解説
集合 S の対象が十分に"構成的"であるとき、ナンバリングは実効的にデコードできるものに注目するのが一般的である（Ershov 1999:486）。例えば S が帰納的可算集合からなるとき、 ナンバリング η が計算可能とは y∈η(x) なる対 (x,y) の集合が帰納的可算であることをいう。同様に部分関数のナンバリング g が計算可能とは関係 R(x,y,z) = "[g(x)](y) = z" が部分帰納的であることをいう（Ershov 1999:487）。 計算可能なナンバリングがprincipalとは任意の計算可能なナンバリングをそれに還元できるときにいう。例えば N {\displaystyle \mathbb {N} } の全てのr.e.部分集合の集合や全ての部分計算可能関数の集合などはprincipalナンバリングを持つ（Ershov 1999:487）。後者についてはしばしばアクセプタブル・ナンバリングと呼ばれる。
※この「計算可能なナンバリング」の解説は、「ナンバリング (計算可能性理論)」の解説の一部です。
「計算可能なナンバリング」を含む「ナンバリング (計算可能性理論)」の記事については、「ナンバリング (計算可能性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「計算可能なナンバリング」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 計算可能なナンバリングのページへのリンク
