ブラウザよりも高速アクセス！
9 関係: マルチタスク、チューリングマシン、タプル、理論計算機科学、確率的チューリング機械、非決定性有限オートマトン、量子コンピュータ、NP完全問題、P≠NP予想。
マルチタスク
マルチタスク (multi tasking) は、コンピュータにおいて複数のタスク（プロセス）を切り替えて実行できるシステムのことである。Unixなど「プロセス」という用語を使うシステムではマルチプロセスともいう（ほぼ同じものを別のシステムでは別の名で呼んでいることもあれば、違うものを同じ名で呼んでいることもあれば、何らかの理由で呼び分けていることもある）。マルチプログラミングという語は複数のプログラムを動かすという点に着目した語である（一般に、「タスク」とか「プロセス」は、プログラムの活動実体、といったようなものを指す語である）。逆に、同時に一つのタスクしか実行できない方式をシングルタスクという。.
新しい！!: 非決定性チューリングマシンとマルチタスク · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: 非決定性チューリングマシンとチューリングマシン · 続きを見る »
タプル
タプルまたはチュープル（tuple）とは、複数の構成要素からなる組を総称する一般概念。 数学や計算機科学などでは通常、順序付けられた対象の並びを表すために用いられる。個別的には、n 個でできた組を英語で「n-tuple」と書き、日本語に訳す場合は通常「n 組」としている。タプルの概念そのものも組と呼ばれる場合がある。なお、 n-tuple は数学のタプルを意味するほか、同様に double、triple などの拡張として倍数詞の表現にも利用される（詳細は「倍#西洋数学における n 倍を表す表現」を参照）。.
新しい！!: 非決定性チューリングマシンとタプル · 続きを見る »
理論計算機科学
論計算機科学（りろんけいさんきかがく、英語：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.
新しい！!: 非決定性チューリングマシンと確率的チューリング機械 · 続きを見る »
非決定性有限オートマトン
非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.
新しい！!: 非決定性チューリングマシンと非決定性有限オートマトン · 続きを見る »
量子コンピュータ
量子コンピュータ （りょうしコンピュータ、英語：quantum computer） は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ（以下「古典コンピュータ」）の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下）で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.
新しい！!: 非決定性チューリングマシンと量子コンピュータ · 続きを見る »
NP完全問題
NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック（Stephen Cook (1971).
新しい！!: 非決定性チューリングマシンとNP完全問題 · 続きを見る »
P≠NP予想
P≠NP予想（P≠NPよそう、）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。P対NP問題（PたいNPもんだい、）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。.
新しい！!: 非決定性チューリングマシンとP≠NP予想 · 続きを見る »
