ブラウザよりも高速アクセス！
21 関係: 原始再帰関数、定理、定義、仮説、チューリングマシン、ラムダ計算、プログラム、アラン・チューリング、アルゴリズム、アロンゾ・チャーチ、エミール・ポスト、クルト・ゲーデル、コンピュータ、ジャック・エルブラン、スティーヴン・コール・クリーネ、計算、計算可能関数、関数、自然数、決定可能性、数論。
原始再帰関数
原始再帰関数（げんしさいきかんすう、）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（限界の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスはwhileプログラムでwhileループを使用せずに計算できる（すなわちloopプログラムで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。.
新しい！!: チャーチ＝チューリングのテーゼと原始再帰関数 · 続きを見る »
定理
定理（ていり、theorem）とは、数理論理学および数学において、証明された真なる命題をいう。 文脈によっては公理も定理に含む。また、数学においては論説における役割等から、補題（ほだい、lemma）あるいは補助定理（ほじょていり、helping theorem）、系（けい、corollary）、命題（めいだい、proposition）などとも呼ばれることがある。ここでの「命題」と冒頭文に言う命題とは意味が異なることに注意。 一般的に定理は、まずいくつかの条件を列挙し、次にその下で成り立つ結論を述べるという形をしている。例えば、次は代数学の基本定理の述べ方の1つである。 ある一定の条件（公理系）下で定理を述べそれを証明すること、というのが数学という分野の中心的な研究の形態である。 数学の多くの分野には、各々「基本定理」という名で呼ばれる中心的な定理が存在している。なお定理という名称と証明という手続きは、数学のみならず、物理や工学においても使用される。.
新しい！!: チャーチ＝チューリングのテーゼと定理 · 続きを見る »
定義
定義（ていぎ）は、一般にコミュニケーションを円滑に行うために、ある言葉の正確な意味や用法について、人々の間で共通認識を抱くために行われる作業。一般的にそれは「○○とは・・・・・である」という言い換えの形で行われる。基本的に定義が決められる場合は1つである。これは、複数の場合、矛盾が生じるからである。.
新しい！!: チャーチ＝チューリングのテーゼと定義 · 続きを見る »
仮説
仮説（かせつ、hypothesis）とは、真偽はともかくとして、何らかの現象や法則性を説明するのに役立つ命題のこと。.
新しい！!: チャーチ＝チューリングのテーゼと仮説 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: チャーチ＝チューリングのテーゼとチューリングマシン · 続きを見る »
ラムダ計算
ラムダ計算（ラムダけいさん、lambda calculus）は、計算模型のひとつで、計算の実行を関数への引数の評価（evaluation）と適用（application）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を（否定的に）解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.
新しい！!: チャーチ＝チューリングのテーゼとラムダ計算 · 続きを見る »
プログラム
プログラム（program; programme, prographein（公示する）から）;一般概念.
新しい！!: チャーチ＝チューリングのテーゼとプログラム · 続きを見る »
アラン・チューリング
アラン・マシスン・チューリング（Alan Mathieson Turing、〔テュァリング〕, 1912年6月23日 - 1954年6月7日）はイギリスの数学者、論理学者、暗号解読者、コンピュータ科学者。.
新しい！!: チャーチ＝チューリングのテーゼとアラン・チューリング · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: チャーチ＝チューリングのテーゼとアルゴリズム · 続きを見る »
アロンゾ・チャーチ
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。.
新しい！!: チャーチ＝チューリングのテーゼとアロンゾ・チャーチ · 続きを見る »
エミール・ポスト
ミール・レオン・ポスト（Emil Leon Post、1897年2月11日 - 1954年4月21日）は、アメリカ合衆国の数学者、論理学者。.
新しい！!: チャーチ＝チューリングのテーゼとエミール・ポスト · 続きを見る »
クルト・ゲーデル
ルト・ゲーデル（Kurt Gödel, 1906年4月28日 - 1978年1月14日）は、オーストリア・ハンガリー二重帝国（現チェコ）のブルノ生まれの数学者・論理学者である。業績には、完全性定理及び不完全性定理、連続体仮説に関する研究が知られる。.
新しい！!: チャーチ＝チューリングのテーゼとクルト・ゲーデル · 続きを見る »
コンピュータ
ンピュータ（Computer）とは、自動計算機、とくに計算開始後は人手を介さずに計算終了まで動作する電子式汎用計算機。実際の対象は文字の置き換えなど数値計算に限らず、情報処理やコンピューティングと呼ばれる幅広い分野で応用される。現代ではプログラム内蔵方式のディジタルコンピュータを指す場合が多く、特にパーソナルコンピュータやメインフレーム、スーパーコンピュータなどを含めた汎用的なシステムを指すことが多いが、ディジタルコンピュータは特定の機能を実現するために機械や装置等に組み込まれる組み込みシステムとしても広く用いられる。電卓・機械式計算機・アナログ計算機については各項を参照。.
新しい！!: チャーチ＝チューリングのテーゼとコンピュータ · 続きを見る »
ジャック・エルブラン
ャック・エルブラン (Jacques Herbrand、1908年2月12日 - 1931年7月27日)はパリ生まれのフランスの数学者である。数理論理学と類体論に業績がある。再帰関数を導入した。エルブランの定理と呼ばれているものは、まったく別の２つの定理を指していう。ひとつは彼が博士論文として書いた証明論についてのものであり、もうひとつはエルブラン・リベットの定理と呼ばれているものである。エルブラン商とはホモロジー代数におけるオイラー標数の一種。彼はまたヒルベルトプログラムにも貢献した（弱い算術系における無矛盾性の証明）。.
新しい！!: チャーチ＝チューリングのテーゼとジャック・エルブラン · 続きを見る »
スティーヴン・コール・クリーネ
ティーヴン・コール・クリーネ（Stephen Cole Kleene, 1909年1月5日 - 1994年1月25日）は、アメリカの数学者。ウィスコンシン大学マディソン校に勤め、その業績は計算機科学の理論的な基礎を築くのに貢献した。クリーネは、正規表現の発明や、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、エミール・ポストらと共に帰納的関数論という数理論理学の一分野を創始したことで知られる。クリーネ代数、クリーネ閉包、クリーネの再帰定理、クリーネ不動点定理の由来になっている。クリーネはまたライツェン・エヒベルトゥス・ヤン・ブラウワーが創始した数学的直観主義に貢献した。 クリーネは自分の姓をクレーニ（（IPA））と発音していた。英語圏ではクリーニ（）、クリーン（）などと誤読されることが多く、日本ではクリーネの表記が一般的になってしまっている。 その数理論理学における傑出した業績は、英語圏の論理学者の間に、"Cleanliness is next to godliness"「清潔さは信心深さに次ぐ」をもじって"Kleeneliness is next to Gödeliness"という格言があることにも表れている。.
新しい！!: チャーチ＝チューリングのテーゼとスティーヴン・コール・クリーネ · 続きを見る »
計算
計算（けいさん）とは、与えられた情報をもとに、命題に従って演繹することである。 これは人間が無意識のレベルで行っている判断（→判断力）や、動物一般が行っている思考を、計算という形で意識化する手法ともいえ、その意味では「ものを考えること」一般が「計算」の一種だとみなすことも可能である。計算に使用される手続きはアルゴリズムと呼ばれる。対人関係において、戦略をアルゴリズムとして状況を有利に運ぶことも時に「計算」と表現される。 もっとも一般的かつ義務教育の範疇で最初に習うものは、算術（算数）における四則演算を、演算記号に示されたアルゴリズム通りに処理するものである。こういった「計算」は日常生活から専門的分野まで幅広く行われており、これを専門に処理する装置や機械も、人類の歴史において数多く開発され利用されている。.
新しい！!: チャーチ＝チューリングのテーゼと計算 · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: チャーチ＝チューリングのテーゼと計算可能関数 · 続きを見る »
関数
関数（かんすう）、函数.
新しい！!: チャーチ＝チューリングのテーゼと関数 · 続きを見る »
自然数
自然数（しぜんすう、natural number）とは、個数、もしくは順番を表す一群の数のことである。集合論においては、自然数は物の個数を数える基数のうちで有限のものであると考えることもできるし、物の並べ方を示す順序数のうちで有限のものであると考えることもできる。 自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる（詳しくは自然数の歴史と零の地位の節を参照）。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。 数学の基礎付けにおいては、自然数の間の加法についての形式的な逆元を考えることによって整数を定義する。正の整数ないしは負でない整数を自然数と同一視し、自然数を整数の一部として取扱うことができる。自然数と同様に整数の全体も可算無限集合である。 なお、文脈によっては、その一群に属する個々の数（例えば 3 や 18）を指して自然数ということもある。.
新しい！!: チャーチ＝チューリングのテーゼと自然数 · 続きを見る »
決定可能性
決定可能（けっていかのう、decidable）は、論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。.
新しい！!: チャーチ＝チューリングのテーゼと決定可能性 · 続きを見る »
数論
数論（すうろん、number theory）とは数、特に整数およびそれから派生する数の体系（代数体、局所体など）の性質について研究する数学の一分野である。整数論とも言う。ふつうは代数学の一分野とみなされることが多い。おおむね次の四つに分けられる。;初等整数論;代数的整数論;解析的整数論;数論幾何学 フェルマーの最終定理のように、数論のいくつかの問題については、他の数学の分野に比して問題そのものを理解するのは簡単である。しかし、使われる手法は多岐に渡り、また非常に高度であることが多い。 ガウスは次のような言葉を残している。.
新しい！!: チャーチ＝チューリングのテーゼと数論 · 続きを見る »
ここにリダイレクトされます：
チャーチ-チューリングの提唱、チャーチのテーゼ、チャーチの提唱、チャーチ・チューリングのテーゼ、チャーチ・チューリングの提唱、チャーチ＝チューリングの提唱。
