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

概要

 チューリング機械(Turing machine)は、概念上の計算機械です。(参照→定義計算機モデル)

 重さや形のある現実の計算機とは異なります。計算するという概念の本質を探るための数学的なモデルです。その定義は、むしろ電子計算機より算盤(そろばん)にたとえた方がずっとわかりやすいです。チューリング機械の模式図としては、良く以下のような描き方がされます。

 何らかの問題を解き解答を得るという作業は、結局は人間が事前に定めたルールに従って、問題を変形させた結果に他ならないのではないか、ともいえます。 例えば、ある数式を因数分解せよといわれたら、結局はその式に対して可能な変形を順次適用して因数分解の結果を得るわけです。厳密にルールに従って変形するだけでしょう。 もし、数学と言う分野に存在する、全てのルールを書物にまとめることが出来れば、近い将来には、数学と言う分野が不要になってしまうかもしれないともいえます。 というのは、順次ルールを適用すると言う作業は、その数式の意味を理解する必要が全く無いからです。ある数学の問題を記述でき、解等を読み上げる能力があればどのような困難な問題も解けてしまうでしょう。

 そのような機械的手続きのルール集は作れるか?という問いかけが数学者ヒルベルトによってなされました。これには、ゲーデルが否定的に結論を見つけてしまったわけですが。チューリングの考えたチューリング 機械もそのような機械的計算手続きの考察から生まれたものに違いありません。

 チューリングは、この機械的手続きを、ルールブック、無限に続くソロバン、ソロバンをはじき続ける操作者、の3部分からなる機会と考えました。

 図中、有限制御部は人間にあたり、ヘッドは人間の手にあたります。テープは算盤本体にあたります。算盤は無限に続いていると考えます。人間は有限な数で表せる状態を持ち、算盤上の数と自分の状態だけから次の行動を全て決めなくてはいけません。人間に許されるのは、算盤上の手を左右に移動することと、算盤をはじくことだけです。人間は途中で方針を変えることなく、算盤の数字に従って定義どおり動きつづけなければなりません。

 今の若い人は算盤を知らなかったりして。おそらく世界最古の計算器でしょう。

 では、チューリング機械などという概念をいったい何に使うのでしょうか?その機能は以下のようなものだと思います。(参照→計算可能性、計算複雑性

 1) ある問題が計算できることを証明する。
 2) ある問題が計算できないことを証明する。
 3) ある問題が短時間で計算できることを証明する。
 4) ある問題が短時間では計算できないことを証明する。

 人間が機械に質問するときは、テープに記号列で問題を書き、チューリング機械はその問題を読み取りながらテープを書き換え(算盤をはじき)つつ答えを出力します。ある問題が本質的に計算不能であることを示すときは、その問題を解くチューリング機械が存在しないことを証明します。

 このような考えの背景にはチャーチの定立(Charch's thesis) があります。(参照→チャーチの定立)一言で言うと、「人間や計算機にできる計算はすべてチューリング機械で計算できる。」ということです。

 人間が数学や哲学などの何らかの表現方法によって解けるはずの問題は必ず解くチューリング機械が存在し、解くチューリング機械が存在しない問題は、誰にも解けない。(参照→言語)これは学者の直感であります。計算可能とか現実的計算可能という言葉もチューリング機械で定義します。(参照→計算可能性)

 ある問題が計算できる(=問題を解くチューリング機械が存在する)ことが自明でも、その問題が簡単に計算できるかどうかがより重要なこともあります。計算が困難であることを示したい場合は、その問題を解く効率の良い(決定性)チューリング機械が存在しないことを証明します。

 問題の複雑さを測る場合に、現実の Work Station や PC を利用して何秒かかるか測るという手段も考えられるでしょう。この場合は、計算機の細かなアーキテクチャやプログラムの実装の稚拙さが結果に反映されるので、「問題が本質的に持っている複雑さ」は見えにくくなります。

 チューリング機械は、細かなアーキテクチャを表面から隠しコンピュータの普遍的で基本的な性質だけで作り出された理想の機械であり、問題の計算不可能性や計算困難性を表現するために時代を問わず利用できる重要な概念です。機械の定義がシンプルなのは、本質以外の部分が取り除かれているからです。(参照→計算複雑性

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

定義

 まず決定性チューリング機械の定義を与えます。(参照→集合関係記号)

定義1)


(Q,Σ,Γ,δ,q0,Fa,Fr) 
が決定性チューリング機械
def
以下 (1-5)を満たす
(1) Q は有限集合   ・・・ Qを状態と呼ぶ
(2) Σ,Γ は有限集合 ・・・ Σ:アルファベット、Γ:テープアルファベット
   * ここで、'_'ÏΣ, Σ⊂Γ ,'_'∈Γ とする ('_' を空白(blanc)という)
(3) q0∈Q           ・・・ q0 を初期状態と呼ぶ
(4) δ:Q×Γ→Q×Γ×{L,R}  ・・・ δを遷移関数と呼ぶ
(5) Fa,Fr⊂Q ,Fa∩Fr=φ  ・・・ Faを受理状態、Frを拒否状態と呼ぶ

 集合 Σアルファベットと呼びます。これは機械に入力文字列(string) を与えるとき使う文字です。テープ長は無限なので、入力文字列の末尾以後は、空白 '_' が書き込まれていると考えます。空白アルファベットに数えません。一方、Γは機械が扱う文字全体をあらわし、テープアルファベットと呼びます。空白テープアルファベットに含まれます。( '_'ÏΣ, '_'∈Γ , Σ⊂Γです。)

 テープは、メモリを概念として扱ったものと考えてください。M はテープに書き込まれている文字 a∈Γを読み取って動作します。遷移関数 δ:Q×Γ→Q×Γ×{L,R} は、有限制御部が置かれている現在の状態 q∈Q と、ヘッドが指し示しているテープ上の文字 a∈Γ が与えられると、一意に新しい状態 q’∈Q と、ヘッドの左右への移動 m∈{L,R}ヘッド位置で書き換える文字 b∈Γ を与えます。このとき δ(,q,a)=(q',b,m) と表記されます。

 この遷移関数はコンピュータの低水準プログラムに相当し、機械 M の動作を決定します。1状態遷移するごとに、1ステップ(時間)を消費します。

 ところで、遷移関数 δ の定義を以下の様に非決定性関数に拡張した機械 M を非決定性チューリング機械(non-deterministic Turing machine) といいます。(参照→関数

定義2)


(Q,Σ,Γ,δ,q0,Fa,Fr) 
が非決定性チューリング機械
def
定義(1)(2)(3)(5)と(4')を満たす
(4') δ:Q×Γ→2Q×Γ×{ L,R }  ・・・ δを遷移関数と呼ぶ

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

特徴

 チューリング機械を特徴付けるとすれば、それは万能チューリング機械が存在するという事実でしょう。計算機モデルとして考えられる多くのモデル、例えば有限オートマトンプッシュダウンオートマトン等に対して万能有限オートマトン万能プッシュダウンオートマトンを作ることは出来ません。

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

様々な定義

 扱う問題によってチューリング機械の定義はいろいろです。最も簡単な定義は、アルファベット Σ を 「0」と「1」に制限したチューリング機械です。使える文字種が多いほうが、制限されているよりも様々な計算が出来そうに思えますが、実は計算できる概念に違いはありません。(多少の計算効率は違うでしょうが)(参照→計算機モデル

 その他に、ヘッドの移動を自由にしてテープ上にランダムアクセスを許した機械としてランダムアクセス機械という定義もあります。こうすると、計算効率はかなり改善されて見えますが、計算できる概念は違いがありません。

 上記図では、テープは右側に無限に伸びている図ですが、左右双方向に無限に伸ばしたチューリング機械を定義することも可能です。実は、双方向に無限に伸ばしても(多少の計算効率を無視すれば)計算の能力は同じです。

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

チューリング機械(Turing machine)

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,

終了,

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