コミュニケーション

7 関係: 帰納言語、チャーチ＝チューリングのテーゼ、チューリングマシン、複雑性クラス、計算複雑性理論、RE (計算複雑性理論)、決定問題。

帰納言語

帰納言語（きのうげんご、Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。.

新しい！!: R (計算複雑性理論)と帰納言語 · 続きを見る »

チャーチ＝チューリングのテーゼ

チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。このクラスはチューリング・マシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。.

新しい！!: R (計算複雑性理論)とチャーチ＝チューリングのテーゼ · 続きを見る »

チューリングマシン

チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.

新しい！!: R (計算複雑性理論)とチューリングマシン · 続きを見る »

複雑性クラス

複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.

新しい！!: R (計算複雑性理論)と複雑性クラス · 続きを見る »

計算複雑性理論

計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.

新しい！!: R (計算複雑性理論)と計算複雑性理論 · 続きを見る »

RE (計算複雑性理論)

計算複雑性理論において、複雑性クラス RE（recursively enumerable）とは、チューリングマシン（Turing machine）で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。 RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。 解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。 RE の各要素は帰納的可算集合（recursively enumerable set）である。.

新しい！!: R (計算複雑性理論)とRE (計算複雑性理論) · 続きを見る »

決定問題

決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.

新しい！!: R (計算複雑性理論)と決定問題 · 続きを見る »

ユニオンペディアは百科事典や辞書のように組織化概念地図や意味ネットワークです。これは、それぞれの概念との関係の簡単な定義を与えます。

これは、概念図の基礎となる巨大なオンライン精神的な地図です。 これを使うのは無料で、各記事やドキュメントをダウンロードすることができます。 それは教師、教育者、生徒や学生が使用できるツール、リソースや勉強、研究、教育、学習や教育のための基準、です。 学問の世界のための：学校、プライマリ、セカンダリ、高校、ミドル、大学、技術的な学位、学部、修士または博士号のために。 論文、報告書、プロジェクト、アイデア、ドキュメント、調査、要約、または論文のために。 ここで定義、説明、またはあなたが情報を必要とする各重要なの意味、および用語集などのそれに関連する概念のリストです。 日本語, 英語, スペイン語, ポルトガル語, 中国の, フランス語, ドイツ語, イタリア語, ポーランド語, オランダ語, ロシア語, アラビア語, ヒンディー語, スウェーデン語, ウクライナ語, ハンガリー語, カタロニア語, チェコ語, ヘブライ語, デンマーク語, フィンランド語, インドネシア語, ノルウェー語, ルーマニア語, トルコ語, ベトナム語, 韓国語, タイ語, ギリシャ語, ブルガリア語, クロアチア語, スロバキア語, リトアニア語, フィリピン人, ラトビア語, エストニア語 と スロベニア語で利用できます。 すぐにその他の言語。

すべての情報は、ウィキペディアから抽出し、それがクリエイティブクリエイティブ・コモンズ 表示-継承ライセンスで利用することができます。

ユニオンペディアはウィキメディア財団の承認を受けておらず、提携もしていません。

Google Play、Android および Google Play ロゴは、Google Inc. の商標です。

個人情報保護方針

出ていきます入ってきます