チューリング機械の解説
    

　　　　　    １　概    要　
　
　Ａ・Ｍ・チューリングは１９３６年に論文を発表し、その中で「計算する」という事を定義し、
  それを証明するための仮想定的な計算機を作り上げました。
　


                      この計算機で計算を行い、この機械がデータを
　　　
　　　      　　　　　　　　　　　出　力

      　　　　　　　　　　　　　　可　能ならば　　計算できる

      　　　　　　　　　　　　　　不可能ならば　　計算できない


この仮想定的な計算機を「チューリング機械」と定義する

       
　チューリング機械は、ある関数を計算するアルゴリズムが存在するか否かという形の問題を、
　数学的に厳密に議論する為に考案された機械で、アルゴリズムによって計算できる関数は
　全て原則的にはチューリング機械によって計算することができ、逆にチューリング機械で
　解けない問題にはアルゴリズムは存在しないと言える。
　つまり、アルゴリズムの判定をする機械がチューリング機械である。 

　では何故チューリング機械がアルゴリズムの判定に使われるのだろうか？
　
　それは、そもそも問題を解くアルゴリズムが存在するということは、問題の解を計算する
　チューリング機械が解を得て停止するという事と同じである。
　従って、「チューリング機械の動作が停止するかどうかを決め得るか？」という問いは、
　アルゴリズムの有無を最も直接的に問いている事になる為である。





　　　     
              ２　構    成



　　�@テープ：外部記憶として記号の書き込みが行われるもの
              計算用紙のようなもので今のコンピュータではメモリの役割をしている
　　　        
              
　　�A記　号：プログラムやデータで、テープに書かれる情報
              テープ中の「1」や「B」を指す
             「B」は空白（blank）を表す特別な記号
              　　　　　　
               
　　�B入出力ヘッド：テープへの読み書きを行う装置
                  
                      　
　　�C本　体：テープ上の情報を読んで計算し、得られた結果を
              テープ上の記号に書き出す






              ３動作原理

                 ステップの動作には明確な定義が必要
　　　　　　　　
  　　                     　　↓
   
                 それは本体が持っている状態関数によって決まる
 
　　　　　
　   　　本体の中に、機能を司る表がインプットされており、それに従って動作する
　　   　例として、加算チューリング機械の遷移表を挙げる




　　　　　これを元にしてチューリング機械は動く

　　　　　状態関数とは状態値を制御する関数で、表中の(S1,1,R)や(S2,B,L)のこと
　　　　　S1やS2は本体の状態(Sは"STATE"の略)、1やBは記号、RとLはヘッドと本体を
　　　　　左右に動かすと言う命令。
　　　　　これらの動作が機械内で行われる。

　　　　　例として



                                                          

　
　　　　　　　　　　　　状態遷移表に従うと
               
      　　　　　　　　　操作Ａ：状態Ｓ０をＳ１にする
　　　　　　　　　　　　　　　　記号１をＢにする

　　　
　　　　　　　　　　　　操作Ｂ：状態Ｓ１をＳ２にする
　　　　　　　　　　　　　　　　記号ＢはＢのまま　  
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　という操作がなされる

　　　　　　　　
　　　　　　また、このときの本体の動きを示すと





          　　　　　　　　　　　　　　　　　　　　　　という動きをする
                    
チューリング機械ではこのような動きが逐次的に行われていく 



トップページに戻る

チューリングさんのページへ

訳文を読みたい

原論文を読みたい

チューリング機械の操作を知る

チューリング機械を動かす