ブラウザよりも高速アクセス！
23 関係: 停止性問題、不動点コンビネータ、マルコフアルゴリズム、チャーチ＝チューリングのテーゼ、チューリングマシン、チューリング還元、バーミンガム大学、ラムダ計算、プログラミング言語、プロシージャ、アルゴリズム、アルゴリズム情報理論、コンピュータ言語、スティーブン・ウルフラム、Brainfuck、無限ループ、計算可能関数、計算可能性理論、計算モデル、計算理論、計算複雑性理論、Lazy K、Smn定理。
停止性問題
計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。.
新しい！!: チューリング完全と停止性問題 · 続きを見る »
不動点コンビネータ
不動点コンビネータ（ふどうてんコンビネータ、fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、fixed-point operator）、パラドキシカル結合子（paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x).
新しい！!: チューリング完全と不動点コンビネータ · 続きを見る »
マルコフアルゴリズム
マルコフアルゴリズム（英: Markov algorithm）とは、記号の文字列に対して一種の文法的規則を適用していく文字列書き換え系である。マルコフアルゴリズムはチューリング完全であることがわかっており、計算の汎用モデルとして使え、任意の数式を単純な記法で表現できる。 Refal はマルコフアルゴリズムに基づいたプログラミング言語である。考案者のアンドレイ・マルコフは、マルコフ連鎖のアンドレイ・マルコフの同名の息子である。.
新しい！!: チューリング完全とマルコフアルゴリズム · 続きを見る »
チャーチ＝チューリングのテーゼ
チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。このクラスはチューリング・マシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。.
新しい！!: チューリング完全とチャーチ＝チューリングのテーゼ · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: チューリング完全とチューリングマシン · 続きを見る »
チューリング還元
チューリング還元（チューリングかんげん、Turing reduction）は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 A が問題 B にチューリング還元されるとは、B が容易に解けると仮定したときに A が容易に解けることを意味する（Rogers 1967、Soare 1987）。より厳密に言えば、B を神託として備えた神託機械によってAが計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。 A から B へのチューリング還元が存在するとき、B を解くあらゆるアルゴリズムは A を解くアルゴリズムを作成するのに使うことが可能である。これは、 A を計算する神託機械が B に関する神託を質問する箇所に B のアルゴリズムを挿入することで実現される。しかし、この神託機械は何回も神託を訊ねる可能性があり、A のアルゴリズムは時間的にも空間的にも B のアルゴリズムよりも計算資源を多く必要とする可能性がある。 アラン・チューリング（1939年）は、神託機械を用いて相対計算可能性（当時は相対還元可能性と称していた）に初めて形式的な定義を与えた。1943年と1952年、スティーヴン・コール・クリーネは同様の概念を帰納的関数を用いて定義した。1944年、エミール・ポストはこの概念を表すのに初めて「チューリング還元可能性（Turing reducibility）」という用語を使った。.
新しい！!: チューリング完全とチューリング還元 · 続きを見る »
バーミンガム大学
バーミンガム大学（University of Birmingham）は、イギリス第2の都市バーミンガムに位置する大学である。 英国の研究型大学で構成されるラッセル・グループの一員であり、現在19,000人を超える学部生および9,000人を超える大学院生が在籍している。卒業生から英国首相、卒業生及び教員から8人のノーベル賞受賞者を輩出している。.
新しい！!: チューリング完全とバーミンガム大学 · 続きを見る »
ラムダ計算
ラムダ計算（ラムダけいさん、lambda calculus）は、計算模型のひとつで、計算の実行を関数への引数の評価（evaluation）と適用（application）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を（否定的に）解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.
新しい！!: チューリング完全とラムダ計算 · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: チューリング完全とプログラミング言語 · 続きを見る »
プロシージャ
プロシージャ （procedure）とは、プログラミングにおいて複数の処理を一つにまとめたものをいう。手続きとするのが定訳である。一連の処理を意味を持った一まとまりにすることで、再利用性が高まり、プログラム中に繰り返して現れる処理を1ヶ所で記述でき、プログラムの保守、管理を容易にする。 繰り返し利用されることから、ルーチンとも言う。呼び出し関係は通常階層構造をなし、その最上位にある、プログラム全体のエントリーポイントを含むルーチンをメインルーチン、呼び出されるものをサブルーチンと言う。また、関数と呼ばれることもある（通常、数学における関数とは違ったものであるので、注意が必要である）。 プログラミング言語により、プロシージャのような構文の分類や呼称はさまざまである。詳細はサブルーチンの記事を参照のこと。 Category:プログラミング言語の構文 he:שגרה ur:دستورالعمل.
新しい！!: チューリング完全とプロシージャ · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: チューリング完全とアルゴリズム · 続きを見る »
アルゴリズム情報理論
アルゴリズム情報理論（あるごりずむじょうほうりろん、Algorithmic information theory）は、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連がある。グレゴリー・チャイティンによれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。.
新しい！!: チューリング完全とアルゴリズム情報理論 · 続きを見る »
コンピュータ言語
ンピュータ言語（コンピュータげんご）とは、コンピュータにおいて用いられる言語の総称である。一般に人工言語で、もっぱら形式言語である（親しみやすさなどの目的で、自然言語風にデザインされることもある）。 プログラムを記述するためのプログラミング言語の一群が最も有名であり、そのため「コンピュータ言語」と「プログラミング言語」は同じ意味で使われることもある。しかし、コンピュータ言語としては他にもハードウェア記述言語や、マークアップ言語のようなデータ記述言語などがあり、それらは「プログラミング言語」ではない。.
新しい！!: チューリング完全とコンピュータ言語 · 続きを見る »
スティーブン・ウルフラム
ティーブン・ウルフラム（Stephen Wolfram、1959年8月29日 - ）は英国人（学部卒業後はアメリカで進学）の理論物理学者で、米ウルフラム・リサーチ社を創業し現在も最高経営責任者である。.
新しい！!: チューリング完全とスティーブン・ウルフラム · 続きを見る »
Brainfuck
Brainfuck（ブレインファック）は難解プログラミング言語のひとつ。なお名称に卑語が含まれるため、Brainf*ckなどと表記されることがある。.
新しい！!: チューリング完全とBrainfuck · 続きを見る »
無限ループ
無限ループ（むげんループ、infinite loop）は、コンピュータ・プログラムの一連の命令が無限に繰り返される（ループする）ことである。永久ループ（えいきゅうループ）ともいう。 専門用語としては一応きちんとした意味があるが、刺激的に感じられる他の用語（例えばメモリリーク）と同様に、通俗的な使い方もされる（「日常会話での使用」を参照）。専門的な意味としての無限ループは、ようだが、実際のところそうではないこともある（#無限ループの検出）。.
新しい！!: チューリング完全と無限ループ · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: チューリング完全と計算可能関数 · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: チューリング完全と計算可能性理論 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: チューリング完全と計算モデル · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: チューリング完全と計算理論 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: チューリング完全と計算複雑性理論 · 続きを見る »
Lazy K
Lazy K（れいじーけー）は組み込み関数が3つしかない、純粋関数型言語である。似た言語として、同じような表記をする、非純粋関数型言語であるUnlambdaがある。.
新しい！!: チューリング完全とLazy K · 続きを見る »
Smn定理
smn定理もしくはパラメータ定理とは、再帰理論における定理であり、プログラミング言語（より一般化すれば、計算可能関数のゲーデル数）の基盤となっている。これを最初に証明したのはスティーブン・コール・クリーネである。s-m-n定理と表記されることもある。 この定理を実用的に解説すると、あるプログラミング言語と正の整数 m と n があるとき、m+n 個の自由変数を持つプログラムのソースコードを操作する特定のアルゴリズムがあることを示している。そのアルゴリズムは、与えられた m 個の値を最初の m 個の自由変数に束縛し、残りの変数を自由変数のままにしておく。.
新しい！!: チューリング完全とSmn定理 · 続きを見る »
