TuringMachine

TuringMachine[rule,init,t]
指定されたルールで初期条件 init から t ステップ進んだチューリングマシンの進化を表すリストを生成する.

TuringMachine[rule,init]
init を1ステップ進化させた結果を与える.

TuringMachine[rule]
進化の1ステップに相当するTuringMachineの演算子形である.

詳細詳細

  • 一次元のチューリングマシンの場合,TuringMachineで生成された進化の各ステップは{{s,x,dx},{a1,a2,}}の形で与えられる.ここで,頭部の状態は s であり,テープ上のセルは値 aiを持ち,頭部は aiと相対的な位置 x にあり,初期位置と比べて dx 動いている.
  • dx がチューリングマシンの初期条件から省略された場合,dx は0とみなされる.
  • d 次元のチューリングマシンでは,テープは d 次元の配列で指定され,位置 x と相対的位置 dx は長さ d のリストになる.
  • チューリングマシンのルールは{si,ai}->{spi,api,offi}の形の置換のリストで与えられる.その要素は次のようになる.
  • si頭部の状態
    ai頭部の下のセルの値
    spi頭部の新しい状態
    api頭部の下のセルの新しい値
    offi頭部が動くオフセット
  • 状態とセルの値は整数,パターン,任意の式のいずれでもよい.個々のセルの値はリストにはできない.
  • 一次元では,各オフセット offiは1個の整数である.次元が高くなると整数のリストになる.
  • 状態とセルの値が,それぞれ1から s までと0から k-1までの範囲の整数であるとされる場合,rule として次の形を与えることができる.
  • nn の状態が2つで色も2色のマシン
    {n,s}n の状態が s 個で色が2色のマシン
    {n,s,k}n の状態が s 個で色が k 色のマシン
    {n,s,k,r}-r から+r の範囲(0を除く)で offiを許容する
    {n,s,k,{r1,r2,,rd}}オフセット+/-r_(1), +/-r_(2), d 次元マシン
    {n,s,k,{{off1},{off2},}}指定された明示的オフセットを許容するマシン
    rule明示的なルールを与えられたマシン
  • 可能なチューリングマシンルールの数は次の通りである.
  • 2状態2色のマシン4096
    s 状態 k 色のマシン(2 s k)^(s k)
    s 状態 k 色で範囲 r のマシン(2 r s k)^(s k)
    二次元で s 状態 k 色のマシン(4 s k)^(s k)
  • マシンがそれ自身が置かれている構造についてのルールを持たない場合,その構造は変化しない.
  • 典型的な初期条件 init の形は次の通りである.
  • {s,{{},0}}頭部の状態 s,0で埋められた一次元テープ上
    {s,{{a1,a2,},0}}無限テープ上の値 aiで区切られた範囲
    {{s,x},{{a1,a2,},0}}頭部が最初は位置 xにある有限範囲
    {{s,},{{a1,},{b1,}}}biの反復する背景
    {{s,},{a1,a2,}}有限テープ,循環を仮定
  • TuringMachine[rule,init,t]は,長さ t+1の進化リストを生成する.
  • TuringMachine[rule][init]TuringMachine[rule,init]に等しい.

例題例題すべて開くすべて閉じる

  (4)  (4)

4つの0からなるテープで始まる,2状態,2色のマシン2506:

In[1]:=
Click for copyable input
Out[1]=

無限の空テープの2状態,2色のマシン2506:

In[1]:=
Click for copyable input
Out[1]=

テープの連続する形状をプロットする:

In[2]:=
Click for copyable input
Out[2]=

チューリングマシンの規則アイコンを生成する:

In[1]:=
Click for copyable input
Out[1]=

ヘッドの位置も含めて進化をプロットする:

In[2]:=
Click for copyable input
Out[2]=

一組の変換規則で返されたマシン:

In[1]:=
Click for copyable input
Out[1]=
2007年に導入
(6.0)
Translate this page: