Meta tags:

Headings (most frequently used words):

帰納的可算集合, 目次, 形式的定義, 等価な定式化, 特性, 注意, 脚注, 参考文献,

Text of the page (most frequently used words):
displaystyle (28), tilde (10), phi (6), #帰納的可算集合 (5), enumerable (4), set (4), 再帰理論 (4), langle (4), rangle (4), 非表示 (4), サイドバーに移動 (4), wikipedia (3), recursively (3), and (3), isbn (3), の元を (3), は帰納的可算である (3), mbox (3), 個の言語版 (2), 目次の表示 (2), 非表示を切り替え (2), コモンズ (2), 計算理論 (2), soare (2), sets (2), degrees (2), logic (2), recursive (2), 参考文献 (2), enumeration (2), アルゴリズム (2), チューリングマシン (2), がそれより前に現れないなら (2), に置く (2), cup (2), subseteq (2), であり (2), である必要十分条件は (2), にあることである (2), ある計算可能関数にゲーデル数 (2), が与えられたとき (2), left (2), right (2), mid (2), downarrow (2), は帰納的可算だが帰納的でない (2), matrix (2), undefined (2), does (2), not (2), halt (2), 等価な定式化 (2), つまり (2), 帰納的可算 (2), 自然数 (2), 形式的定義 (2), あるいは (2), 履歴を表示 (2), ツール (2), ログイン (2), アカウント作成 (2), ヘルプ (2), メインメニュー (2), 話題を追加, モバイルビュー, cookieに関する声明, 開発者, 行動規範, 法律および安全に関する連絡先, 免責事項, ウィキペディアについて, プライバシー, ポリシー, テキストは, のもとで利用できます, 追加の条件が適用される場合があります, 詳細については, を参照してください, 利用規約, クリエイティブ, 継承ライセンス, ページは, によってレンダリングされました, parsoid, 最終更新, 2025年12月31日, 日時は, で未設定ならば, utc, 個人設定, 隠しカテゴリ, isbnマジックリンクを使用しているページ, 数学に関する記事, 数理論理学, カテゴリ, から取得, https, org, index, php, title, oldid, 107822582, robert, 1978, 1149, 1181, bull, amer, math, soc, springer, verlag, berlin, 1987, 540, 15299, perspectives, mathematical, rogers, mit, press, 053522, 262, 68052, the, theory, functions, effective, computability, richard, friedberg, 1958, 309, 316, journal, symbolic, three, theorems, decomposition, maximal, iii, without, duplication, 最近の文献では, 帰納的可算集合を全体再帰関数の, ではなく, 部分関数の, 定義域, として定義する方が一般的である, この理由は, 例えば, のような一般化された再帰理論では, 定義域を用いた定義の方が自然だと判ったためである, 他の文献では枚挙を使った定義がよく使われるが, これも帰納的可算集合に同値である, によれば, 実効的に計算可能な関数は全て, で計算可能であり, 従って集合, が帰納的可算である必要十分条件は, 何らかの, の枚挙ができることである, しかしこれを形式的な定義とすることはできない, 何故ならチャーチ, チューリングのテーゼは形式的な公理ではなく, 非形式的な予想だからである, チャーチ, チューリングのテーゼ, 任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる, 任意の帰納的可算集合, に対して, 互いに素な帰納的可算集合, なるものが存在する, と交互に枚挙していく, このとき, は所望の性質を満たす, ldots, 互いに素な帰納的可算集合同士の対を取ると, あるものは, あるものは帰納的分離不可能である, 対照的に, 任意の互いに素な, 集合対が帰納的分離可能であることが, 次の性質から示される, 帰納的分離可能, 計算可能, の補集合が共に帰納的可算集合であることである, これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す, すなわち補元を持つ元が帰納的可算集合である, ある集合が帰納的である必要十分条件は, その集合が何らかの単調増加な全域再帰関数の値域になっているか, または有限なことである, 帰納的, が帰納的可算である場合, と呼ばれる, 同様に, ある集合が, それが算術的階層のレベル, mathbb, setminus, 補集合, ある集合が帰納的可算である必要十分条件は, それが, のレベル, sigma, 算術的階層, が共に帰納的可算集合なら, も帰納的可算集合である, 部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である, 自然数から自然数への部分関数, があるとき, が部分再帰関数である必要十分条件は, が定義されるような全ての対, の集合が帰納的可算であることである, この集合は関数値を決定する問題の符号化である, lbrace, rbrace, ここで, が定義されていることを示す, この集合は, が停止する入力パラメータ群を表すことで, の符号化となる, チューリングマシンの停止問題, 対関数, は帰納的可算ではない, 生産的集合, 創造的集合, 単純集合, マチャセビッチの定理によれば, 全ての帰納的可算集合はディオファントス集合である, 逆も明らかに真, 帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である, の帰納的可算な部分集合である, 形式言語, 帰納的可算言語, 全ての, は帰納的可算だが, 全ての帰納的可算集合が帰納的, とは言えない, 帰納的集合, 最後の性質は, 最初の定義から単純に導かれるものではないが, を否定的に解決する過程で, が発見した, ディオファントス集合は, に先行しているため, 歴史的にはこれが帰納的可算集合の最初の定義であった, ただし, これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである, 上記の式における, の個数は, これまでのところ最小とされているもので, もっと少ない個数でディオファントス集合を表せる可能性はある, 束縛変数, ユーリ, マチャセビッチ, ヒルベルトの第10問題, 整数群から整数群への多項式があり, はその値域の非負数だけを正確に含む, leftrightarrow, exists, 次のような整数係数の多項式, があり, の値域が自然数全体に及んでいる, ディオファントス方程式, の値域であるか空である, が無限であっても, 単射とはならない, 原始再帰関数, 全体再帰関数の値域であるか空である, が無限の場合, その関数は, でもよい, 部分再帰関数の値域である, 可算性, begin, notin, end, 次のような部分再帰関数, が存在する, すなわち, はある部分再帰関数の定義域である, 半決定可能性, 以下は, 自然数の集合, について同じ特性を表現したものである, この定義は任意の可算集合, に拡張できる, そのためには, で表し, もし対応するゲーデル数の集合が帰納的可算ならば, の何らかの部分集合が帰納的可算になることを言えば良い, ゲーデル数, の集合, について, 定義域が, と正確に一致するような何らかの部分再帰関数, が存在するとき, であると言う, が定義される必要十分条件は, への入力が, の元であることである, 部分計算可能関数, において, 全ての帰納的可算集合を包含する, と呼ぶ, においては, 包含関係に基づく, 集合の, lattice, と書く, mathcal, 複雑性クラス, 計算複雑性理論, これが, semidecidable, と時に呼ばれるのは前者の条件に由来する, computably, という用語は後者の条件に由来する, 略して, と書くが, これは出版物にもよく出現する, 計算可枚挙集合, 半決定可能集合, するアルゴリズムが存在する, その出力は, の元のリスト, である, このアルゴリズムは必要ならば無限に動作する, これと同値だが, に入力となる数を与えたとき, そのアルゴリズムが停止する必要十分条件が, その数が, であることである, きのうてきかさんしゅうごう, または, におけるある種の, に付与された名前, について以下が成り立つ場合, その集合を指して, などと称する, チューリング, 認識可能, 証明可能, 半決定可能, 計算可枚挙, フリー百科事典, ウィキペディア, ウィキデータ項目, 他のプロジェクト, 印刷用バージョン, pdf, 形式でダウンロード, ブックの新規作成, 書き出し, レガシーパーサーに切り替え, 短縮urlを取得する, このページを引用, ページ情報, この版への固定リンク, ファイルをアップロード, 関連ページの更新状況, リンク元, 日本語, ノート, ページ, リンクを編集, русский, português, 한국어, italiano, עברית, français, español, esperanto, english, deutsch, чӑвашла, العربية, ページ先頭, 個人用ツール, ウィキペディアに関するお問い合わせ, バグの報告, お知らせ, 井戸端, 利用案内, 特別ページ, アップロード, ウィキメディア, 練習用ページ, おまかせ表示, 最近の更新, 新しいページ, 最近の出来事, コミュニティ, ポータル, メインページ, コンテンツにスキップ,

Text of the page (random words):
帰納的可算集合 wikipedia コンテンツにスキップ メインメニュー メインメニュー サイドバーに移動 非表示 案内 メインページ コミュニティ ポータル 最近の出来事 新しいページ 最近の更新 おまかせ表示 練習用ページ アップロード ウィキメディア コモンズ 特別ページ ヘルプ ヘルプ 利用案内 井戸端 お知らせ バグの報告 ウィキペディアに関するお問い合わせ 検索 検索 表示 寄付 アカウント作成 ログイン 個人用ツール 寄付 アカウント作成 ログイン 目次 サイドバーに移動 非表示 ページ先頭 1 形式的定義 2 等価な定式化 3 例 4 特性 5 注意 6 脚注 7 参考文献 目次の表示 非表示を切り替え 帰納的可算集合 13 個の言語版 العربية чӑвашла deutsch english esperanto español français עברית italiano 한국어 português русский 中文 リンクを編集 ページ ノート 日本語 閲覧 編集 履歴を表示 ツール ツール サイドバーに移動 非表示 操作 閲覧 編集 履歴を表示 全般 リンク元 関連ページの更新状況 ファイルをアップロード この版への固定リンク ページ情報 このページを引用 短縮urlを取得する レガシーパーサーに切り替え 印刷 書き出し ブックの新規作成 pdf 形式でダウンロード 印刷用バージョン 他のプロジェクト ウィキデータ項目 表示 サイドバーに移動 非表示 出典 フリー百科事典 ウィキペディア wikipedia 帰納的可算集合 きのうてきかさんしゅうごう 英 recursively enumerable set は 計算理論 または 再帰理論 におけるある種の 集合 に付与された名前 自然数 の 集合 s について以下が成り立つ場合 その集合を指して 帰納的可算 計算可枚挙 半決定可能 証明可能 チューリング 認識可能 などと称する ある アルゴリズム に入力となる数を与えたとき そのアルゴリズムが停止する必要十分条件が その数が s の 元 であることである あるいは これと同値だが s の元を 枚挙 するアルゴリズムが存在する つまり その出力は s の元のリスト s 1 s 2 s 3 である このアルゴリズムは必要ならば無限に動作する これが 半決定可能集合 semidecidable set と時に呼ばれるのは前者の条件に由来する また 計算可枚挙集合 computably enumerable set という用語は後者の条件に由来する 略して r e あるいは c e と書くが これは出版物にもよく出現する 計算複雑性理論 において 全ての帰納的可算集合を包含する 複雑性クラス を re と呼ぶ 再帰理論 においては 包含関係に基づく r e 集合の 束 lattice を e displaystyle mathcal e と書く 形式的定義 編集 自然数 の集合 s について 定義域が s と正確に一致するような何らかの部分再帰関数 部分計算可能関数 f が存在するとき s は 帰納的可算 であると言う つまり f が定義される必要十分条件は f への入力が s の元であることである この定義は任意の可算集合 a に拡張できる そのためには a の元を ゲーデル数 で表し もし対応するゲーデル数の集合が帰納的可算ならば a の何らかの部分集合が帰納的可算になることを言えば良い 等価な定式化 編集 以下は 自然数の集合 s について同じ特性を表現したものである 半決定可能性 集合 s は帰納的可算である すなわち s はある部分再帰関数の定義域である 次のような部分再帰関数 f が存在する f x 0 if x s undefined does not halt if x s displaystyle f x left begin matrix 0 mbox if x in s mbox undefined does not halt mbox if x notin s end matrix right 可算性 集合 s は 部分再帰関数の値域である 集合 s は 全体再帰関数の値域であるか空である s が無限の場合 その関数は 単射 でもよい 集合 s は 原始再帰関数 の値域であるか空である s が無限であっても 単射とはならない ディオファントス方程式 次のような整数係数の多項式 p があり 変数 x a b c d e f g h i の値域が自然数全体に及んでいる x s a b c d e f g h i p x a b c d e f g h i 0 displaystyle x in s leftrightarrow exists a b c d e f g h i p x a b c d e f g h i 0 整数群から整数群への多項式があり 集合 s はその値域の非負数だけを正確に含む 最後の性質は 最初の定義から単純に導かれるものではないが ヒルベルトの第10問題 を否定的に解決する過程で ユーリ マチャセビッチ が発見した ディオファントス集合は 再帰理論 に先行しているため 歴史的にはこれが帰納的可算集合の最初の定義であった ただし これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである 上記の式における 束縛変数 の個数は これまでのところ最小とされているもので もっと少ない個数でディオファントス集合を表せる可能性はある 例 編集 全ての 帰納的集合 は帰納的可算だが 全ての帰納的可算集合が帰納的 集合 とは言えない 帰納的可算言語 は 形式言語 の帰納的可算な部分集合である 帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である マチャセビッチの定理によれば 全ての帰納的可算集合はディオファントス集合である 逆も明らかに真 単純集合 は帰納的可算だが帰納的でない 創造的集合 は帰納的可算だが帰納的でない 生産的集合 は帰納的可算ではない ある計算可能関数にゲーデル数 ϕ displaystyle phi が与えられたとき 集合 i x ϕ i x displaystyle langle i x rangle mid phi _ i x downarrow は帰納的可算である ここで i x displaystyle langle i x rangle は 対関数 であり ϕ i x displaystyle phi _ i x downarrow は ϕ i x displaystyle phi _ i x が定義されていることを示す この集合は チューリングマシン が停止する入力パラメータ群を表すことで チューリングマシンの停止問題 の符号化となる ある計算可能関数にゲーデル数 ϕ displaystyle phi が与えられたとき 集合 x y z ϕ x y z displaystyle lbrace left langle x y z right rangle mid phi _ x y z rbrace は帰納的可算である この集合は関数値を決定する問題の符号化である 自然数から自然数への部分関数 f があるとき f が部分再帰関数である必要十分条件は f x が定義されるような全ての対 x f x displaystyle langle x f x rangle の集合が帰納的可算であることである 特性 編集 a と b が共に帰納的可算集合なら a b a b a b も帰納的可算集合である 部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である ある集合が帰納的可算である必要十分条件は それが 算術的階層 のレベル σ 1 0 displaystyle sigma _ 1 0 にあることである 集合 t displaystyle t の 補集合 n t displaystyle mathbb n setminus t が帰納的可算である場合 t displaystyle t は co r e と呼ばれる 同様に ある集合が co r e である必要十分条件は それが算術的階層のレベル π 1 0 displaystyle pi _ 1 0 にあることである 集合 a が 帰納的 計算可能 である必要十分条件は a と a の補集合が共に帰納的可算集合であることである これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す すなわち補元を持つ元が帰納的可算集合である ある集合が帰納的である必要十分条件は その集合が何らかの単調増加な全域再帰関数の値域になっているか または有限なことである 互いに素な帰納的可算集合同士の対を取ると あるものは 帰納的分離可能 であり あるものは帰納的分離不可能である 対照的に 任意の互いに素な co r e 集合対が帰納的分離可能であることが 次の性質から示される 任意の帰納的可算集合 a b displaystyle a b に対して 互いに素な帰納的可算集合 a b displaystyle tilde a tilde b で a a displaystyle tilde a subseteq a b b displaystyle tilde b subseteq b a b a b displaystyle tilde a cup tilde b a cup b なるものが存在する a b displaystyle a b の元を a 0 b 0 a 1 b 1 displaystyle a_ 0 b_ 0 a_ 1 b_ 1 ldots と交互に枚挙していく a i displaystyle a_ i がそれより前に現れないなら a displaystyle tilde a に置く また b i displaystyle b_ i がそれより前に現れないなら b displaystyle tilde b に置く このとき a b displaystyle tilde a tilde b は所望の性質を満たす 任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる 1 注意 編集 チャーチ チューリングのテーゼ によれば 実効的に計算可能な関数は全て チューリングマシン で計算可能であり 従って集合 s が帰納的可算である必要十分条件は 何らかの アルゴリズム で s の枚挙ができることである しかしこれを形式的な定義とすることはできない 何故ならチャーチ チューリングのテーゼは形式的な公理ではなく 非形式的な予想だからである 最近の文献では 帰納的可算集合を全体再帰関数の 値域 ではなく 部分関数の 定義域 として定義する方が一般的である この理由は 例えば α 再帰理論 en のような一般化された再帰理論では 定義域を用いた定義の方が自然だと判ったためである 他の文献では枚挙を使った定義がよく使われるが これも帰納的可算集合に同値である 脚注 編集 richard m friedberg 1958 three theorems on recursive enumeration i decomposition ii maximal set iii enumeration without duplication journal of symbolic logic 23 3 pp 309 316 参考文献 編集 rogers h the theory of recursive functions and effective computability mit press isbn 0 262 68052 1 isbn 0 07 053522 1 soare r recursively enumerable sets and degrees perspectives in mathematical logic springer verlag berlin 1987 isbn 3 540 15299 7 soare robert i recursively enumerable sets and degrees bull amer math soc 84 1978 no 6 1149 1181 https ja wikipedia org w index php title 帰納的可算集合 oldid 107822582 から取得 カテゴリ 数理論理学 計算理論 数学に関する記事 隠しカテゴリ isbnマジックリンクを使用しているページ 最終更新 2025年12月31日 水 23 03 日時は 個人設定 で未設定ならば utc ページは parsoid によってレンダリングされました テキストは クリエイティブ コモンズ 表示 継承ライセンス のもとで利用できます 追加の条件が適用される場合があります 詳細については 利用規約 を参照してください プライバシー ポリシー ウィキペディアについて 免責事項 法律および安全に関する連絡先 行動規範 開発者 統計 cookieに関する声明 モバイルビュー 検索 検索 目次の表示 非表示を切り替え 帰納的可算集合 13 個の言語版 話題を追加