Team TripleFalcon. http://www.triplefalcon.com/

概要

 計算するとは何か、計算できるとはどういうことか突き詰めていった結果、得られた一つの成果が概念上の計算機です。計算論を知らない多くの人が、チューリング機械(Turing machine) とか有限オートマトン(finite automata) の名前は知っています。計算したいと考える問題の程度にあわせていろいろな計算機の定義を用いることがあります。

 まず、普通に定義された決定性のチューリング機械を考えたとき能力を余計に付加してみたいと考えたとします。動作に、非決定動作とか確率動作を付加したモデルが、以下の様になります。

 動作が決定性(deterministic)非決定性(non-deterministic)確率的(probablistic) による分類があります。特殊な場合には量子機械(quantum) というのも考える場合があります。最も普通の機械は決定性機械であり、それ以外の機械は今のところ概念上しか存在しません。

名称 概要
交互機械 次の動作を非決定的に決める(全称関数、存在関数)
非決定性機械 次の動作を非決定的に決める(存在関数)
確率機械 次の動作が確率的に決まる
決定性機械 次の動作が一意に決まる
量子機械 動作状態が、量子力学的に「重畳された」まま動作

 反対に、チューリング機械に制限を加えることでより弱い機械を考えてもかまわないわけです。入力された質問の長さに対して機械が使ってよい記憶領域について制限を与えると、大体は以下のような分類がされます。下へ行くほど記憶領域が制限され、動作の自由度が失われています。(受理する言語は、機械が非決定機械の場合)このようなモデルを研究すると、記憶領域とは何かについて理解を与えてくれる場合があります。

名称 略称 受理する言語 概要
チューリングマシン TM 成句構造言語 (参照→チューリング機械)
線形有界オートマトン LBA 文脈依存言語 入力の定数倍まで領域を使える
プッシュダウンオートマトン PDA 文脈自由言語 スタックの頂上へのアクセスのみ
有限オートマトン FA 正則言語 固定された記憶領域しかない

 上記の略称に対して、動作が決定的動作でないモデルには接頭辞 N- が付くことがあります。プッシュダウンオートマトン非決定性なら NPDA と表記し、チューリング機械量子動作可能なら、QTM と表記します。交互機械は A-とします。

 その他、チューリング機械の記憶テープをいろいろ工夫して、以下のような計算機モデルを考える場合もあります。下のシリーズは単純なチューリング機械に能力を付加したと考えればよいでしょう。

名称 概要
kテープ機械 記憶テープの本数を k 本にする
kレジスタ機械 テープでなく、自然数記憶可能なレジスタを扱う
ランダムアクセス機械 配列の直接アクセスを可能にしてしまう

Team TripleFalcon. http://www.triplefalcon.com/

非決定性機械

 決定性機械というのは、現在の状態から次の状態が一意に決まる機械です。従って、我々が知っている普通の計算機は決定性機械です。

 非決定性機械は、計算機モデルでは最初につまずく概念かもしれません。非決定性機械というのは、そのような機械が実現できると予想されているような概念ではなくて、現実の能力を超越した理想化された機械です。そのような概念と、決定性の(いわゆる現実の)機械と比較することで新たな理解を得ることを目的として考えています。(参照→非決定性計算)

 チューリング機械 M=(Q,Σ,Γ,δ,q0,Fa,Fr) の動作を決定するのは、遷移関数δですが、δが非決定性関数の場合に非決定性チューリング機械と呼ばれます。同様に、有限オートマトンなど他のモデルに対しても非決定性動作の能力を与えてみることもあります。(参照→チューリング機械、非決定性関数)

Team TripleFalcon. http://www.triplefalcon.com/

確率機械

 遷移関数δに確率重みをつけ、確率的に次の状態へ遷移するように設計したモデルを確率機械といいます。この概念は、高速な素数判定など暗号学では重要な概念も多く生み出しています。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

計算機モデル(models)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール