1999年から2008年における発展
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/03 07:15 UTC 版)
「K自明集合」の記事における「1999年から2008年における発展」の解説
計算可能性理論の文脈において、コスト関数とは計算可能関数で を満たすものを言う。ある集合Aの計算可能な近似に対し、上記の関数はステージsでA(n)の近似を変化させるコストc(n,s)を測っている。最初のコスト関数の構成はクチェラとテルワインによる。彼らはc.e.集合でマルティンレーフランダム低だが計算可能ではないものを構成した。ここで、コスト関数は作られる集合の計算可能な近似に依存している。c.e.だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文による。 集合Aがコスト関数cに従うとは、Aの計算可能な近似が存在して、 を満たすことを言う。K自明集合は以下で定義される標準コスト関数に従う集合として特徴付けられる。 ここで、であり、はある固定した普遍接頭機械の計算可能近似におけるsステップである。
※この「1999年から2008年における発展」の解説は、「K自明集合」の解説の一部です。
「1999年から2008年における発展」を含む「K自明集合」の記事については、「K自明集合」の概要を参照ください。
ウィキペディア小見出し辞書の「1999年から2008年における発展」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 1999年から2008年における発展のページへのリンク
