TuringMachine

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

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

詳細詳細

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

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

  (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)