翻訳と辞書
Words near each other
・ 再帰反射板
・ 再帰可能
・ 再帰呼び出し
・ 再帰型
・ 再帰性
・ 再帰熱
・ 再帰理論
・ 再帰的
・ 再帰的に枚挙可能
・ 再帰的アルゴリズム
再帰的可算集合
・ 再帰的定義
・ 再帰的頭字語
・ 再度
・ 再度ドライブウエイ
・ 再度公園
・ 再度公園及び再度山永久植生保存地
・ 再度協議
・ 再度山
・ 再度山ドライブウェイ


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

再帰的可算集合 : ミニ英和和英辞書
再帰的可算集合[さいき]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [さい]
  1. (pref) re- 2. again 3. repeated 
再帰 : [さいき]
 (n) recursive
: [まと, てき]
 【名詞】 1. mark 2. target 
: [か]
  1. (n,n-suf) passable 
: [しゅう]
 【名詞】 1. collection 
集合 : [しゅうごう]
  1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set 
: [ごう]
 【名詞】 1. go (approx. 0.18l or 0.33m) 

再帰的可算集合 ( リダイレクト:帰納的可算集合 ) : ウィキペディア日本語版
帰納的可算集合[きのうてきかさんしゅうごう]
帰納的可算集合(きのうてきかさんしゅうごう、)は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数集合 ''S'' について以下が成り立つ場合、その集合を指して帰納的可算計算可枚挙半決定可能証明可能チューリング-認識可能などと称する。
* あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が ''S'' の元であることである。
あるいは、これと同値だが、
* ''S'' の元を枚挙するアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''1, ''s''2, ''s''3, ... である。このアルゴリズムは必要ならば無限に動作する。
これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合(computably enumerable set)という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。
計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスRE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の (lattice) を \mathcal と書く。
== 形式的定義 ==
自然数の集合 ''S'' について、定義域が ''S'' と正確に一致するような何らかの部分再帰関数(部分計算可能関数)''f'' が存在するとき、''S'' は帰納的可算であると言う。つまり ''f'' が定義される必要十分条件は、''f'' への入力が ''S'' の元であることである。
この定義は任意の可算集合 A に拡張できる。そのためには、A の元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「帰納的可算集合」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Recursively enumerable set 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.