頻度計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
再帰理論のこの分野が扱ったのは、次の問題である。0 < m < n であるような定数 m,n があるとする。関数の集合 A があるとして、n 個の任意の異なる入力 x1,x2,...,xn について、少なくとも m 個の等式 A(xk) = yk が真となるように、n 組の数字 y1,y2,...,yn を計算できるだろうか？ そのような集合は (m,n)-再帰集合と呼ばれる。再帰理論のこの方面における最初の主要な成果は Trakhtenbrot が得た結果で、それによればある集合が 2m > n であるような m,n について (m,n)-再帰的であるとき、その集合は計算可能である。その一方で、Jockusch の semirecursive 集合（Jockusch が1968年に導入する以前から非形式的には知られていた）は、(m,n)-再帰的である必要十分条件が 2m < n+1 であるような集合の例である。このような集合は非可算個存在し、また帰納的可算だが計算不可能な集合でこの性質を持つものも存在する。後に Degtev は (1,n+1)-再帰的だが (1,n)-再帰的ではないような帰納的可算集合を階層状に分類した。ロシア人の科学者達による研究が長年続いた後、この話題は Beigel の限定付きクエリ (bounded queries) に関する命題によって再び注目を集めた。Beigel の命題は頻度計算と上に述べた限定付き還元可能性や他の関連概念を結び付けた。主な結果の一つとして Kummer の濃度理論がある。それによれば集合 A が計算可能となる必要十分条件は次の性質を満たす n が存在することである。即ち何らかのアルゴリズムを用いて、n 個の異なる数字から成る組について、この n 個の数字の集合と A との積集合が取り得る濃度の候補を n 種類まで数え上げることができる（これらの候補は正しい濃度を必ず含むが、少なくとも一つは間違った濃度が混ざる）。
※この「頻度計算」の解説は、「再帰理論」の解説の一部です。
「頻度計算」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
- 頻度計算のページへのリンク
