ブラウザよりも高速アクセス！
20 関係: 位取り記数法、形式言語、ペアノの公理、チューリングマシン、レーヴェンハイム–スコーレムの定理、ダグラス・ホフスタッター、アルゴリズム、エンコード、クルト・ゲーデル、ゲーデルの不完全性定理、ゲーデル、エッシャー、バッハ、シンボル、算術の基本定理、群 (数学)、計算可能性理論、計算モデル、自然数、Well-formed formula、推論規則、数理論理学。
位取り記数法
位取り記数法（くらいどりきすうほう）、もしくは「N 進法」とは数の表現方法の一種で、予め定められたN 種類の記号（数字）を列べることによって数を表す方法である。(位取りのことを桁ともいう。) 今日の日本において通常使われているのは、 N が十のケースである十進法であるが、コンピューターでは二進法、八進法、十六進法なども用いられる。また歴史的には、十進法が世界的に広まったのはフランス革命の革命政府がメートル法とともに十進法を定めて以来であり、それ以前は国や分野により、様々な N に対する N 進法が用いられていた。 本項ではN が自然数の場合を扱う。それ以外の場合については広義の記数法の記事を参照のこと。また 後述する''p''進数の概念とは（関連があるものの）別概念であるので注意が必要である。.
新しい！!: ゲーデル数と位取り記数法 · 続きを見る »
形式言語
形式言語（けいしきげんご、formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
新しい！!: ゲーデル数と形式言語 · 続きを見る »
ペアノの公理
ペアノの公理（ペアノのこうり、Peano axioms） とは、自然数全体を公理化したものである。1891年に、ジュゼッペ・ペアノによって定義された。.
新しい！!: ゲーデル数とペアノの公理 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: ゲーデル数とチューリングマシン · 続きを見る »
レーヴェンハイム–スコーレムの定理
レーヴェンハイム–スコーレムの定理（Löwenheim–Skolem theorem）とは、可算な一階の理論が無限モデルを持つとき、全ての無限濃度 κ について大きさ κ のモデルを持つ、という数理論理学の定理である。そこから、一階の理論はその無限モデルの濃度を制御できない、そして無限モデルを持つ一階の理論は同型の違いを除いてちょうど1つのモデルを持つようなことはない、という結論が得られる。.
新しい！!: ゲーデル数とレーヴェンハイム–スコーレムの定理 · 続きを見る »
ダグラス・ホフスタッター
ダグラス・リチャード・ホフスタッター（Douglas Richard Hofstadter、1945年2月15日 - ）はニューヨーク生まれのアメリカの学者。2014年現在、インディアナ大学ブルーミントン校教授。専門は認知科学および計算機科学。ホフスタッターは多くの一般書を執筆しており、その中でも特に有名なのが『ゲーデル、エッシャー、バッハ - あるいは不思議の環』(1979)。 ホフスタッターは1980年に同書でピュリッツァー賞の一般ノンフィクション部門を受賞した。この本は人工知能の問題を高エネルギー物理学、音楽、芸術、分子生物学、文学、といった多彩なテーマに絡めて記述し、多くの人々の興味を惹いた。この本がきっかけになって、人工知能分野へ進むことを決めた学生も大勢いると言われている。.
新しい！!: ゲーデル数とダグラス・ホフスタッター · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ゲーデル数とアルゴリズム · 続きを見る »
エンコード
ンコード（encode）、符号化（ふごうか）とは、アナログ信号やデジタルデータに特定の方法で、後に元の（あるいは類似の）信号またはデータに戻せるような変換を加えることである。 一般的には、エンコードするための機器・回路・プログラムをエンコーダ、デコード（記事内後述を参照）するための機器・回路・プログラムをデコーダと呼んでいる。 特にコンピュータ（特にパーソナルコンピュータ）分野では、エンコードとは、音声や動画などをコーデックを用いて圧縮する事を言う。一部では「エンコ」と略して呼ぶこともある。.
新しい！!: ゲーデル数とエンコード · 続きを見る »
クルト・ゲーデル
ルト・ゲーデル（Kurt Gödel, 1906年4月28日 - 1978年1月14日）は、オーストリア・ハンガリー二重帝国（現チェコ）のブルノ生まれの数学者・論理学者である。業績には、完全性定理及び不完全性定理、連続体仮説に関する研究が知られる。.
新しい！!: ゲーデル数とクルト・ゲーデル · 続きを見る »
ゲーデルの不完全性定理
ーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.
新しい！!: ゲーデル数とゲーデルの不完全性定理 · 続きを見る »
ゲーデル、エッシャー、バッハ
『ゲーデル、エッシャー、バッハ - あるいは不思議の環』（ダグラス・ホフスタッター著、野崎昭弘、はやしはじめ、柳瀬尚紀 訳、原題は Gödel, Escher, Bach: an Eternal Golden Braid）は、1979年に米国で刊行された一般向けの科学書。単に GEB とも呼ばれる。（邦題では『ゲーデル，エッシャー，バッハ』と「，」が使われる） 1985年に白揚社から日本語訳が発行され、1980年代後半から90年代前半にかけて日本でも小ブームが起きた。1980年ピューリッツァー賞受賞。.
新しい！!: ゲーデル数とゲーデル、エッシャー、バッハ · 続きを見る »
シンボル
国のシンボルとして国旗が掲げられる。（南極点の南極条約加盟国の旗） 各種宗教のシンボル。 シンボル は、記号 を分類した1つの種類である。その厳密な定義は1つではないが、記号のうちその対象との関係が非本来的・隠然的であるものがシンボルとされる。「象徴記号」と訳されることもある。"symbol"の語源は古代ギリシャ語の"symbolon"(σύμβολον) に由来し、syn-が「一緒に」、boleが「投げる」や「飛ばす」を意味し、合わせて、「一緒にする」や、二つに割ったものをつき合わせて同一の物と確認する「割符」や「合言葉」を意味する。.
新しい！!: ゲーデル数とシンボル · 続きを見る »
算術の基本定理
pp.
新しい！!: ゲーデル数と算術の基本定理 · 続きを見る »
群 (数学)
数学における群（ぐん、group）とは最も基本的と見なされる代数的構造の一つである。群はそれ自体興味深い考察対象であり、群論における主要な研究対象となっているが、数学や物理学全般にわたってさまざまな構成に対する基礎的な枠組みを与えている。.
新しい！!: ゲーデル数と群 (数学) · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: ゲーデル数と計算可能性理論 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: ゲーデル数と計算モデル · 続きを見る »
自然数
自然数（しぜんすう、natural number）とは、個数、もしくは順番を表す一群の数のことである。集合論においては、自然数は物の個数を数える基数のうちで有限のものであると考えることもできるし、物の並べ方を示す順序数のうちで有限のものであると考えることもできる。 自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる（詳しくは自然数の歴史と零の地位の節を参照）。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。 数学の基礎付けにおいては、自然数の間の加法についての形式的な逆元を考えることによって整数を定義する。正の整数ないしは負でない整数を自然数と同一視し、自然数を整数の一部として取扱うことができる。自然数と同様に整数の全体も可算無限集合である。 なお、文脈によっては、その一群に属する個々の数（例えば 3 や 18）を指して自然数ということもある。.
Well-formed formula
数理論理学において well-formed formula（wff、整式などとも）とは、形式言語といったような概念が広まる以前に、"formula" を単なる「記号を任意の順序に並べたもの」であるとして、それらのうち、数式などとして意味をなすような記号列を特に区別したものである。形式言語の考え方が広まるにつれ、そもそも意味のある数式などは何らかのルールに従って導出されるもので、それ以外の、任意の順序に並べたようなものは最初から議論の対象外として扱われるのが普通となった。.
新しい！!: ゲーデル数とWell-formed formula · 続きを見る »
推論規則
推論規則（すいろんきそく、rule of inference, inference rule, transformation rule）とは、論理式から他の論理式を導く推論の規則である。 記号、公理、代入規則、推論規則によって理論を形式化したものを公理系という。 公理は記号だけで記述されるが、推論規則や代入規則はこれらの記号について述べているメタ言語で記述される。 恒真式 （トートロジー）から推論規則を導くと妥当性のある推論になる。.
新しい！!: ゲーデル数と推論規則 · 続きを見る »
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
新しい！!: ゲーデル数と数理論理学 · 続きを見る »
