ブラウザよりも高速アクセス！
57 関係: 停止性問題、反復補題、学問の一覧、実数型、不動点定理、帰納的分離不能対、二重再帰法、低基底定理、ナンバリング、チューリング完全、チューリングマシン、チューリングジャンプ、チューリング次数、ポストの定理、ユーリ・マチャセビッチ、ラムダ計算、ロバート・ローゼン、ビジービーバー、ディオファントス方程式、デジタル物理学、制御構造、アラン・チューリング、アルゴリズム、クリストファー・ラングトン、グジェゴルチク階層、ケーニヒの補題、ゲーデルの不完全性定理、ゲーデル数、コンビネータ論理、コンピューティング、シミュレーション仮説、セル・オートマトン、再帰理論、知識表現、理論計算機科学、確率的チューリング機械、神託機械、EXPTIME、複雑性クラス、計算可能関数、計算理論、計算複雑性理論、計算機科学、論、論理学の歴史、還元 (計算複雑性理論)、量子コンピュータ、Goto文、Μ再帰関数、K自明集合、...、Zuse Z3、抽象解釈、極限計算可能関数、構成主義 (数学)、情報学、数学、数論の有効な結果。 インデックスを展開 (7 もっと) »
停止性問題
計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。.
新しい！!: 計算可能性理論と停止性問題 · 続きを見る »
反復補題
反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。.
新しい！!: 計算可能性理論と反復補題 · 続きを見る »
学問の一覧
学問の一覧（がくもんのいちらん）は、大学・大学院レベルで学ばれる学問分野を分類したものである。それぞれの分野には下位分野があり「（例）物理学→素粒子物理学」、この下位分野にはそれぞれ学術雑誌、学会があることが多い。 学問の分類には図書分類法のような分類法がなく、日本とアメリカ、ヨーロッパなど地域や教育機関ごとに差異がある。例えば法学を社会科学に含める場合もあればそうでない場合もある。 今日ますます各学問に分野横断的な傾向が強まるなかで、ある学問を単一の分野に分類することが困難な場合が多くなっている（学際研究）。.
新しい！!: 計算可能性理論と学問の一覧 · 続きを見る »
実数型
実数型（じっすうがた）の記事では、コンピュータプログラミングにおいて実数の近似を表現するデータ型について説明する。実数は可算無限集合でないため、有限の量を正確に表すことしかできないコンピュータで、実数を正確に表現することは基本的には不可能であり、「実数型」という語自体は、数値表現の難しさが甘く考えられていた1960年代のプログラミング言語などで見られた歴史的表現、ないし、現代のものならば数式処理システムなどを除けば、ちゃんと考えていれば浮動小数点数型というような名前を使っているが、そうでない場合などに実数型という語を使っている場合もある。コンピュータの数値表現の記事も参照。.
新しい！!: 計算可能性理論と実数型 · 続きを見る »
不動点定理
数学における不動点定理（ふどうてんていり、fixed-point theorem）は、ある条件の下で自己写像 は少なくとも 1 つの不動点 （ となる点 ）を持つことを主張する定理の総称を言う。不動点定理は応用範囲が広く、分野を問わず様々なものがある。.
新しい！!: 計算可能性理論と不動点定理 · 続きを見る »
帰納的分離不能対
計算可能性理論において帰納的分離不能対（きのうてきぶんりふのうつい、recursively inseparable pair)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ1集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。.
新しい！!: 計算可能性理論と帰納的分離不能対 · 続きを見る »
二重再帰法
二重再帰法（にじゅうさいきほう、double recursion）とは再帰関数論において、アッカーマン関数の様な原始再帰では無い関数を定義を可能にする原始再帰法(primitive recursion)の拡張である。 は2つの自然数を持つ G(n, x) の様な関数を二重再帰的（double recursive）と呼んだ。それは次の様な関数だった。.
新しい！!: 計算可能性理論と二重再帰法 · 続きを見る »
低基底定理
計算可能性理論における低基底定理（low basis theorem）は 2^ の任意の空でない\Pi^0_1クラス（算術的階層を見よ）は低次数の元を含むことを示す（Soare 1987:109）もので、1972年にカール・ショカシュとロバート・アーヴィング・ソーアによって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると \Pi^0_1 クラスの理論において最も引用されている結果"と記している。 この定理の証明には \Pi^0_1 クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では 0'-構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際には超低次数の元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。 \Pi^_クラスは木の概念と密接に関係している。\Pi^_クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低い無限枝を持つ」ことを述べている。.
新しい！!: 計算可能性理論と低基底定理 · 続きを見る »
ナンバリング
ナンバリング (numbering).
新しい！!: 計算可能性理論とナンバリング · 続きを見る »
チューリング完全
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」それはチューリング完全ではない。 コンピュータ言語のうち、少なくともチューリング完全でなければプログラミング言語とは呼ばれない。逆にチューリング完全であるにも関わらず慣例的にプログラミング言語とは呼ばれないものもある。.
新しい！!: 計算可能性理論とチューリング完全 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: 計算可能性理論とチューリングマシン · 続きを見る »
チューリングジャンプ
チューリングジャンプ（Turing jump または Turing jump operator）とは、計算可能性理論におけるある数学的な操作に付与された名前。名称はアラン・チューリングに因む。直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。 この作用素は問題 X のチューリング次数を増やす（ジャンプさせる）ので「ジャンプ作用素」と呼ばれる。つまり問題 X’は X にチューリング還元可能ではない。 ポストの定理はチューリングジャンプ作用素と自然数の集合の算術的階層との関係を明らかにしている。.
新しい！!: 計算可能性理論とチューリングジャンプ · 続きを見る »
チューリング次数
チューリング次数（～じすう、Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。 任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 X のチューリング次数が集合 Y のチューリング次数よりも小さいならば、ある数が Y に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が X に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。 チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。.
新しい！!: 計算可能性理論とチューリング次数 · 続きを見る »
ポストの定理
ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。.
新しい！!: 計算可能性理論とポストの定理 · 続きを見る »
ユーリ・マチャセビッチ
ユーリ・マチャセビッチ（、Yuri Matiyasevich、1947年3月2日 - ）は、ロシアの数学者、計算機科学者。サンクトペテルブルク生まれ（当時はレニングラード）。ヒルベルトの23の問題の中の第10問題を否定的に解いたことで知られている。.
新しい！!: 計算可能性理論とユーリ・マチャセビッチ · 続きを見る »
ラムダ計算
ラムダ計算（ラムダけいさん、lambda calculus）は、計算模型のひとつで、計算の実行を関数への引数の評価（evaluation）と適用（application）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を（否定的に）解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.
新しい！!: 計算可能性理論とラムダ計算 · 続きを見る »
ロバート・ローゼン
バート・ローゼン (Robert Rosen, 1934年6月27日 – 1998年12月28日) はアメリカの理論生物学者。「生命とは何か?」 という問いを独特の哲学的、数理的な考察の元で探究し、関係生物学 (relational biology) と呼ばれる枠組みにおいて定式化しようと試みた。 ニューヨークブルックリン区生まれ。コロンビア大学で数学を学んだ後、シカゴ大学で数理生物学への研究に転じ、ニコラス・ラシェフスキー (Nicholas Rashevsky) に学んで彼の関係生物学の概念に強い影響を受けた。 ニューヨーク州立大学バッファロー校を経て、1975年より退官までカナダ、ハリファックスのダルハウジー大学で生物物理を教えた。ニューヨーク州ロチェスターで死去。.
新しい！!: 計算可能性理論とロバート・ローゼン · 続きを見る »
ビジービーバー
ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。 ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、ティボール・ラドーによる1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。.
新しい！!: 計算可能性理論とビジービーバー · 続きを見る »
ディオファントス方程式
ディオファントス方程式（ディオファントスほうていしき、Diophantine equation）とは、整係数多変数高次不定方程式である。文脈として、整数解や有理数解を問題にしたい場合に用いられる用語であり、主に数論の研究課題と考えられている。古代アレクサンドリアの数学者ディオファントスの著作『算術』で、その有理数解が研究されたのにちなんだ名称である。.
新しい！!: 計算可能性理論とディオファントス方程式 · 続きを見る »
デジタル物理学
デジタル物理学（デジタルぶつりがく、digital physics）とは、「宇宙は本質的に情報により記述可能であり、それ故、計算可能である」という仮定によって導かれる、物理学及び宇宙論における理論的展望の総称である。このような仮定を立てるとき、宇宙は、コンピュータプログラムの出力、あるいはある種の巨大なデジタル計算デバイスとして理解される。 デジタル物理学は、以下の一つ以上の仮説を基礎としている。なお、記載の順番はその主張の強さを示す。.
新しい！!: 計算可能性理論とデジタル物理学 · 続きを見る »
制御構造
制御構造（せいぎょこうぞう）は、コンピュータ・プログラミング言語、特に手続き型プログラミングや命令型プログラミングにおいて、ループや飛び越しなどといった、手続き（プロシージャ）中の実行順を順次実行から変化させたり、サブルーチン呼出しやその戻り、などといった制御を行う「文 (プログラミング) 」などの構造（言語の構成要素）である。 制御構造の種類は言語によって様々だが、典型的には以下のようなものがある（用語「ブロック」については、ブロック (プログラミング) の記事を参照）。.
新しい！!: 計算可能性理論と制御構造 · 続きを見る »
アラン・チューリング
アラン・マシスン・チューリング（Alan Mathieson Turing、〔テュァリング〕, 1912年6月23日 - 1954年6月7日）はイギリスの数学者、論理学者、暗号解読者、コンピュータ科学者。.
新しい！!: 計算可能性理論とアラン・チューリング · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: 計算可能性理論とアルゴリズム · 続きを見る »
クリストファー・ラングトン
リストファー・ラングトン（Christopher Langton、1949年 - ）は、アメリカ合衆国の計算機科学者。人工生命の研究で知られる。1980年代後半、「Artificial Life（人工生命）」という用語を生み出し、1987年に "International Conference on the Synthesis and Simulation of Living Systems"（通称、Artificial Life I）という国際会議をロスアラモス国立研究所で開催した。 ミシガン大学を卒業後、ラングトンはラングトンのアリとラングトンのループという単純な人工生命シミュレーションを作るとともに、セル・オートマトンの複雑性と計算可能性の無次元の尺度であるλ（ラムダ）パラメータを考案した。2状態、1-r 近傍、1次元のセル・オートマトンでのその値はほぼ 0.5 となる。ライフゲームのような 2状態、ムーア近傍、2次元のセル・オートマトンでは、0.273 となる。このλパラメータの研究から「カオスの縁」という用語が生まれた。 ラングトンは、"Homer Kelly Mysteries" などの著作で知られる作家ジェーン・ラングトンの長男である。.
新しい！!: 計算可能性理論とクリストファー・ラングトン · 続きを見る »
グジェゴルチク階層
ェゴルチク階層（ぐじぇごるちくかいそう、Grzegorczyk hierarchy、発音：）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。.
新しい！!: 計算可能性理論とグジェゴルチク階層 · 続きを見る »
ケーニヒの補題
ラフ理論におけるケーニヒの補題はデネス・ケーニヒ (1936)によって示された定理で、 無限グラフが無限長の道をもつための十分条件を与える。 この定理のcomputability aspectsは数理論理学の計算可能性理論の研究者によって調べられてきている。 この定理は構成的数学や証明論においても重要な役割をもつ。.
新しい！!: 計算可能性理論とケーニヒの補題 · 続きを見る »
ゲーデルの不完全性定理
ーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.
新しい！!: 計算可能性理論とゲーデルの不完全性定理 · 続きを見る »
ゲーデル数
ーデル数（ゲーデルすう、Gödel number）は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。クルト・ゲーデルが不完全性定理の証明に用いたことから、このように呼ばれている。また、ゲーデル数を割り振ることをゲーデル数化（Gödel numbering）と呼ぶ。 ゲーデル数のアイデアを暗に使っている例としては、コンピュータにおけるエンコードが挙げられる。 コンピュータでは何でも0と1で表し、「apple」のような文字列も0と1による数字で表す。 ゲーデル数化とは、このように文字列に数字を対応させる事を指す。 ゲーデル数化は、数式におけるシンボルに数を割り当てる符号化の一種でもあり、それによって生成された自然数の列が文字列を表現する。この自然数の列をさらに1つの自然数で表現することもでき、自然数についての形式的算術理論を適用可能となる。 ゲーデルの論文が発表された1931年以来、ゲーデル数はより広範囲な様々な数学的オブジェクトに自然数を割り振るのに使われるようになっていった。.
新しい！!: 計算可能性理論とゲーデル数 · 続きを見る »
コンビネータ論理
ンビネータ論理(Combinatory Logic、組み合わせ論理)は、（Моисей Эльевич Шейнфинкель、Moses Ilyich Schönfinkel）とハスケル・カリー（Haskell Brooks Curry）によって、記号論理での変数を消去するために導入された記法である。最近では、計算機科学において計算の理論的モデルで利用されてきている。また、関数型プログラミング言語の理論（意味論など）や実装にも応用がある。 コンビネータ論理は、コンビネータまたは引数のみからなる関数適用によって結果が定義されている高階関数、コンビネータに基づいている。.
新しい！!: 計算可能性理論とコンビネータ論理 · 続きを見る »
コンピューティング
階差機関。多項式関数の解を計算する機械 とある大学の計算機室 (2003) ウィキメディア財団のサーバ コンピューティング（computing）の古来の意味は「数えること」と「計算すること」であり、算術ないしは数学の計算を指した。現在は転じてコンピュータによる数値計算や、より広くデータ処理(data processing)や情報処理 (information processing) といったコンピュータを使う活動全般も指すことがある。 日本語ではどちらも「計算」と呼んでいるが、対応する英語にはcalculationとcomputationがある。条件分岐などを伴う複雑な計算がcalculationではなくcomputationである。.
新しい！!: 計算可能性理論とコンピューティング · 続きを見る »
シミュレーション仮説
ミュレーション仮説（シミュレーションかせつ）とは、人類が生活しているこの世界は、すべてシミュレーテッドリアリティであるとする仮説のこと。シミュレーション理論と呼ぶ場合もある。.
新しい！!: 計算可能性理論とシミュレーション仮説 · 続きを見る »
セル・オートマトン
Daniel Dennett (1995), ''Darwin's Dangerous Idea'', Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X セル・オートマトン（cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「homogeneous structure」「tessellation structure」「iterative array」といった呼称もある。 有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t においてのセルの状態、および近傍のセルの内部状態によって、次の時刻t+1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 t.
新しい！!: 計算可能性理論とセル・オートマトン · 続きを見る »
再帰理論
再帰理論（さいきりろん、Recursion theory）は、数理論理学の一分野で、1930年代の計算可能関数とチューリング次数の研究が源となっている。発展の過程で、この分野は計算可能性や定義可能性全般を対象に含むようになった。これらの領域においては、再帰理論は証明論や effective 記述集合論(en)とも密接に関係する。 再帰理論の根本的疑問は「自然数から自然数への関数が計算可能であるとはどういう意味か?」と、「計算不能関数は、その計算不能性のレベルに基づいて階層分けできるか?」である。これらの疑問への答えを探す過程で豊かな理論が生まれ、現在でも活発な研究が行われている。 数理論理学における再帰理論の研究者がよく扱うのは、この記事で触れる相対的な計算可能性、還元性の概念、次数構造などである。これらは、計算機科学における計算可能性理論が、計算複雑性理論、形式手法、形式言語などを主な研究対象とすることと対照を成す。これら二つの研究コミュニティには知識と手法の面で重なる部分が多々あり、はっきりした境界を引くことは出来ない。.
新しい！!: 計算可能性理論と再帰理論 · 続きを見る »
知識表現
知識表現（ちしきひょうげん）、KR（Knowledge Representation）は、推論を導けるような知識の表現、およびその方法を開発する人工知能研究の領域である。 思考を形式的に分析し、議論領域を記述する。一般に、議論領域の記述から推論するための形式意味論を与え、解釈可能な意味を各文が生じるように演算子を与える。それによって自動推論が可能となる。 知識表現は、表現力が高いほど、事柄が簡潔に記述されるが、一貫性が保障されず、自動推論が困難となる。例として、命題論理は自己認識的時相論理よりも表現力が低い。用途・必要性・資源との適合性がKR推論システムの開発において大切となる。 最近の主な知識表現の研究としてセマンティック・ウェブがある。XML型言語の知識表現と標準の開発に随伴することが多い。.
新しい！!: 計算可能性理論と知識表現 · 続きを見る »
理論計算機科学
論計算機科学（りろんけいさんきかがく、英語：theoretical computer science）は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、現実のコンピュータを扱うことも多いが、チューリングマシンなどの計算モデルを扱うことも多い。 理論計算機科学の代表的な分野として以下のものがある。.
新しい！!: 計算可能性理論と理論計算機科学 · 続きを見る »
確率的チューリング機械
率的チューリング機械（かくりつてきチューリングきかい、Probabilistic Turing machine）は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。 各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット（一般に '1' と '0'）についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。 結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。 従って、確率的チューリング機械での文字列の受理/不受理は、通常とは異なった形で定義される。この定義の違いによって、様々な多項式時間の確率的な複雑性クラスが生じる。例えば、'''RP'''、Co-RP、'''BPP'''、ZPP などである。制約を多項式時間ではなく対数領域とした場合は、LP、Co-RL、BPL、ZPL がある。また、両方を制約を課した場合は、RLP、Co-RPL、BPLP、ZPLP がある。 確率的計算は対話型証明系の多くのクラスの定義においても重要である。この場合、検査機構（verifier）は全能の証明機構（prover）にだまされないためにランダム性を必要とする。例えば、IPクラスは PSPACE に等しいが、検査機構でのランダム性を排除すると NP と等しくなってしまう。PSPACE と NP の関係は正確には未だ確定していないが、おそらく NP の方が小さいと考えられている。 計算複雑性理論の課題の1つとして、「ランダム性は計算能力を向上させるか?」という問題がある。つまり、確率的チューリング機械で多項式時間で解ける問題があるとき、それが決定性チューリング機械では多項式時間で解けないと言えるだろうか? それとも、決定性チューリング機械で確率的チューリング機械をシミュレートして、高々多項式程度の低速化で問題を解けるだろうか? 現在、多くの研究者は後者（P.
新しい！!: 計算可能性理論と確率的チューリング機械 · 続きを見る »
神託機械
託機械（しんたくきかい、oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。.
新しい！!: 計算可能性理論と神託機械 · 続きを見る »
EXPTIME
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。 DTIMEでは次のように表される。 以下の関係が知られている。 また、時間階層定理と領域階層定理により、次のようになる。 従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P.
新しい！!: 計算可能性理論とEXPTIME · 続きを見る »
複雑性クラス
複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.
新しい！!: 計算可能性理論と複雑性クラス · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: 計算可能性理論と計算可能関数 · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: 計算可能性理論と計算理論 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: 計算可能性理論と計算複雑性理論 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: 計算可能性理論と計算機科学 · 続きを見る »
論
論（ろん）とは、ある事象に対し順序立てられた思考・意見・言説をまとめた物である。.
論理学の歴史
論理学の歴史では妥当な推論を探求する学問の発展を取り扱う。形式論理学は古代の中国、インド、ギリシアで発展した。ギリシア論理学、中でもアリストテレス論理学は科学・数学に広く受容・応用されている。 アリストテレス論理学は中世のイスラーム圏およびキリスト教西方世界にさらに発展し、14世紀半ばに頂点をむかえた。14世紀から19世紀初めまでの時期は概して論理学が衰退し、軽視された時期であり、少なくとも一人の論理学史家によって論理学の不毛期とみなされているOxford Companion p. 498; Bochenski, Part I Introduction, passim。 19世紀半ばになると論理学が復興し、革命期が始まって、数学において用いられる厳密な証明を手本とする厳格かつ形式的な規則へと主題が発展した。近現代におけるこの時期の発展、いわゆる「記号」あるいは「数理」論理学は二千年にわたる論理学の歴史において最も顕著なものであり、人類の知性の歴史において最も重要・顕著な事件の一つだと言えるOxford Companion p. 500。 数理論理学の発展は20世紀の最初の数十年に、特にゲーデルおよびタルスキの著作によって起こり、分析哲学や哲学的論理学に、特に1950年代以降に様相論理や時相論理、義務論理、適切さの論理といった分野に影響を与えた。.
新しい！!: 計算可能性理論と論理学の歴史 · 続きを見る »
還元 (計算複雑性理論)
還元（かんげん、Reduction）とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。 直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。.
新しい！!: 計算可能性理論と還元 (計算複雑性理論) · 続きを見る »
量子コンピュータ
量子コンピュータ （りょうしコンピュータ、英語：quantum computer） は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ（以下「古典コンピュータ」）の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下）で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.
新しい！!: 計算可能性理論と量子コンピュータ · 続きを見る »
Goto文
プログラミング言語におけるgoto文（ゴートゥぶん、goto statement）とは、手続き列中の指定された場所（専らラベルで指定される）に無条件にジャンプ（移動）する、という制御構造のひとつである「文 (プログラミング) 」である。古い文献などで "go to" と離していることもあるのは、英語の go to どこそこ、といったような言い回しとの類似のためでもあり、FORTRANではプログラム中の空白は基本的に無視されるので、goto でも go to でも同じだったからという理由もある（BASICにも、どちらも使えるようにしているものもある）。.
新しい！!: 計算可能性理論とGoto文 · 続きを見る »
Μ再帰関数
μ再帰関数（ミューさいきかんすう、μ-recursive function）または帰納的関数（きのうてきかんすう）は、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。 計算複雑性理論では、全再帰関数の集合を'''R'''と称する。.
新しい！!: 計算可能性理論とΜ再帰関数 · 続きを見る »
K自明集合
数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、K-trivial set）であるとは、 そのを2進文字列と見た時に記述しやすいことを言う。 すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。 は1975年に計算不可能なK自明集合の存在を示した。 によれば、ランダムな集合の始切片は高い複雑性を持つ。 つまり、K自明集合はランダムからかけ離れているということである。 そのため、ランダムネスの理論で研究されており、 計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。 例えば、それらはすべてである、つまり、そのチューリングジャンプが停止問題に真理表還元可能である。 また、を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。.
新しい！!: 計算可能性理論とK自明集合 · 続きを見る »
Zuse Z3
Zuse Z3 のレプリカ（ミュンヘンドイツ博物館） Zuse Z3は、1941年にドイツでコンラート・ツーゼによって開発された計算機である。世界初の自由にプログラム可能で完全に自動化された機械である。現代の視点からすると、コンピュータの定義に適合する属性をほぼ備えているが、条件分岐命令を備えていない。Z3は2200個のリレーから構成され、動作周波数はおおよそ5から10Hz、ワード長は 22ビットである。プログラムとデータはセルロイド製のフィルムに穴を開けることで記憶される。 1941年にベルリンで完成し、ドイツ航空機研究所で翼のフラッター現象の統計解析に使われた。 本来の Z3 は1943年のベルリン爆撃で破壊された。完全に動作する複製が1960年代にツーゼの会社 Zuse KG によって作成され、ドイツ博物館に永久展示されている。 ツーゼはドイツ政府にリレーを電子スイッチに置き換えるための資金提供を要請したが、第二次世界大戦中であり、戦争遂行の観点から重要でないと判断され、資金は得られなかった。.
新しい！!: 計算可能性理論とZuse Z3 · 続きを見る »
抽象解釈
抽象解釈（ちゅうしょうかいしゃく、Abstract interpretation）は、コンピュータプログラムの意味論の健全な近似の理論であり、順序集合（特に束）における単調関数に基づいている。全ての計算を実施することなく、プログラムの部分的な実行（ある種の部分評価）をするものと見ることができ、それによりプログラムの意味に関する情報（例えば、制御構造、情報の流れなど）を獲得する。 主な応用として、形式的な静的コード解析があり、プログラム実行に関する情報を自動抽出するものである。このような解析には次の2つの利用法がある。.
新しい！!: 計算可能性理論と抽象解釈 · 続きを見る »
極限計算可能関数
計算可能性理論における極限計算可能関数(きょくげんけいさんかのうかんすう、limit computabile function)とは、一様に計算可能な関数列の極限によって表せる関数をいう。極限において計算可能(computable in the limit)や極限帰納的(limit recursive)などともいう。集合が極限計算可能とはその特性関数が極限計算可能であることをいう。 関数列が D-計算可能であるとき、極限の関数は D-極限計算可能であるという。.
新しい！!: 計算可能性理論と極限計算可能関数 · 続きを見る »
構成主義 (数学)
数学の哲学において、構成主義（こうせいしゅぎ、constructivism）とは、「ある数学的対象が存在することを証明するためには、それを実際に見つけたり構成したりしなければならない」という考えのことである。標準的な数学においてはそうではなく、具体的に見つけることなしに背理法によって存在を示す、すなわち存在しないことを仮定して矛盾を導くことがよくある。この背理法というものは構成的に見ると十分ではない。構成的な見地は、古典的な解釈をもって中途半端なままである、存在記号の意味を確かめることを含む。 多くの形の構成主義がある 。これらはブラウワーによって創始された数学的直観主義のプログラム、ヒルベルトならびにベルナイスの、ならびにの構成的で再帰的な数学、そしてであるのプログラムを含む。構成主義はやトポス論の研究のようなの研究もまた含む。 構成主義はしばしば直観主義と同一視される、しかしながら直観主義は構成主義者のプログラムのひとつでしかない。個人的な数学者の直観のなかに数学の基礎がおかれるところの直観主義数学は、それによってひとつの内在的で主観的な活動のなかへと数学をさせている 。他の形の構成主義は直観のこの見地において基礎をもたない、そして数学において客観的な見地をもって両立できる。.
新しい！!: 計算可能性理論と構成主義 (数学) · 続きを見る »
情報学
情報学（じょうほうがく）という語が指す学術分野は、基本的には情報に関する分野であるが、歴史的な事情により、特に英語と日本語の対応があいまいである。もともとは図書館学の一部である、書誌情報の管理・検索を由来とする情報や知識を扱う分野がコンピュータの発展などで大きくなったため、図書館情報学（Library and Information Science）と呼ぶようになった分野があり、その場合の「情報学」は「Information Science」である（Library and Information Scienceという成語に気付かず、「図書館と情報科学」と訳されている場合がある）。一方、社会情報学（social informatics）やバイオインフォマティクス（生命情報学）等といった「～informatics」＝「～情報学」と呼ばれている分野もあるが、その場合の「情報学」は「Informatics」である（インフォマティクスも参照）。.
新しい！!: 計算可能性理論と情報学 · 続きを見る »
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
新しい！!: 計算可能性理論と数学 · 続きを見る »
数論の有効な結果
数論の結果をディオファントス方程式の解法へ応用するためには、論理が計算可能か否かを、数学の他の分野より精密に精査する。これには歴史的理由がある。整数の一覧が有限であると主張されているとき、問題はその一覧を原理的に計算機で計算した後にプリントアウトできるかどうかでということある。.
新しい！!: 計算可能性理論と数論の有効な結果 · 続きを見る »
