チューリングマシンとは

/数学基礎

チューリングマシンとは

チューリングマシンとは、計算を行うための基本的な機能が定義された、仮想的な装置です。チューリングマシンは、計算可能性の議論を行うため、数学者チューリングにより1936年に考案されました。

チューリングマシンの構造

チューリングマシンの構造は非常にシンプルで、制御部(以下、ヘッド)と十分な長さを持つ記憶部(以下、テープ)により構成されます。ヘッドは有限個の命令を順番に実行します。

テープはマス目に分かれており、それぞれ記号が設置されています。ここで記号は、ビット(2進数)を表す「1」と「0」の他、テープの左端を表す「#」、空白を表す「b」などを定義します。

チューリングマシンの動作

チューリングマシンの命令

チューリングマシンの命令もシンプルで、次の4つで構成されます。

  • ヘッドの位置にあるマス目の記号を読む(resd)
  • ヘッドの位置にあるマス目に記号を書く(write)
  • ヘッドの位置を左右どちらかのマス目に移動させる(move)
  • 次の新しい命令に進む(goto)

例えば、最初のビットを反転させる命令(I1)は以下のように表されます。ここで、「halt」は処理の終了を表します。

命令 記号の読出し
(read)
記号の書込み
(write)
ヘッドの移動
(move)
次の命令
(goto)
I1





right
right
right
halt
I1
I1
I1
チューリングマシンの実行例

ヘッドの開始位置を左端として、この命令を実行させると以下のようになります。初期のテープの状態を「#1010b1・・・」として、ヘッドの位置をマス目の左側に[I1]として書いています。

[I1]#1010b1
#[I1]1010b1
#0[I1]010b1
#01[I1]10b1
#010[I1]0b1
#0101[I1]b1
#0101b1

以上のように、4ビットの反転をするのに、6ステップの命令を実行していることが分かります。

万能チューリングマシン

万能チューリングマシンとは、他のチューリングマシンの動作を模倣する能力を有するチューリングマシンです。

万能チューリングマシン($M_u$)は、整数の組 $i$ と $x$ を入力として、入力 $x$ に対するチューリングマシン($M_i$)の計算を実行します。これを式で表すと以下になります。

$$M_u(i,x)=M_i(x)$$

万能チューリングマシンはテープを2本使用し、1本のテープは $M_i(x)$ の計算を実行するために使用され、もう1本のテープは $M_i$ の命令記述(プログラム)を格納するために使われます。

 

応用数学
物理数学、計算数学、情報・暗号、機械学習、金融工学、ゲーム理論
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

 

タイトルとURLをコピーしました