Mathematica 9 is now available
SEARCH MATHEMATICA 8 DOCUMENTATION
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Mathematica > 計算システム >
Mathematica 組込みシンボル関連項目 »|その他 »

TuringMachine

TuringMachine[rule, init, t]
指定されたルールで初期条件init からt ステップ進んだチューリングマシンの進化を表すリストを生成する．
TuringMachine[rule, init]
init を1ステップ進化させた結果を与える．
  • 1次元のチューリングマシンの場合， 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頭部が動くオフセット
  • 状態とセルの値は整数，パターン，任意の式のいずれでもよい．個々のセルの値はリストにはできない．
  • 1次元では，各オフセットoffi は1個の整数である．次元が高くなると整数のリストになる．
  • 状態とセルの値が，それぞれ1からs までと0からk-1までの範囲の整数であるとされる場合，rule として次の形を与えることができる．
n数 n の状態が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)
2次元で s 状態 k 色のマシン(4 s k)^(s k)
  • マシンがそれ自身が置かれている構造についてのルールを持たない場合，その構造は変化しない．
  • 典型的な初期条件init の形は次の通りである．
{s,{{},0}}頭部の状態 s，0で埋められた1次元テープ上
{s,{{a1,a2,...},0}}無限テープ上の値 ai で区切られた範囲
{{s,x},{{a1,a2,...},0}}頭部が最初は位置 xにある有限範囲
{{s,...},{{a1,...},{b1,...}}}値 bi の反復する背景
{{s,...},{a1,a2,...}}有限テープ，循環を仮定
  • TuringMachine[rule, init, t]は，長さt+1の進化リストを生成する．
例題すべて閉じる
例   (4)
4つの零からなるテープで始まる，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]=
 
1組の変換規則で返されたマシン：
In[1]:=
Click for copyable input
Out[1]=
バージョン 6 の新機能
© 2013 Wolfram Research, Inc. English
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team