Mathematica 9 is now available
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
Mathematica > 数学とアルゴリズム > 計算システム > TuringMachine >
Mathematica > 数学とアルゴリズム > 離散数学 > 計算システム > TuringMachine >
MATHEMATICA 組込みシンボル関連項目 »|その他 »

TuringMachine

TuringMachine
指定されたルールで初期条件 init から t ステップ進んだチューリングマシンの進化を表すリストを生成する．
TuringMachine
init を1ステップ進化させた結果を与える．
詳細
  • 一次元のチューリングマシンの場合， TuringMachineで生成された進化の各ステップはの形で与えられる．ここで，頭部の状態は s であり，テープ上のセルは値 を持ち，頭部は と相対的な位置 x にあり，初期位置と比べて dx 動いている．
  • dx がチューリングマシンの初期条件から省略された場合，dx は0とみなされる．
  • d 次元のチューリングマシンでは，テープは d 次元の配列で指定され，位置 x と相対的位置 dx は長さ d のリストになる．
  • チューリングマシンのルールはの形の置換のリストで与えられる．その要素は次のようになる：
si頭部の状態
ai頭部の下のセルの値
spi頭部の新しい状態
api頭部の下のセルの新しい値
offi頭部が動くオフセット
  • 状態とセルの値は整数，パターン，任意の式のいずれでもよい．個々のセルの値はリストにはできない．
  • 一次元では，各オフセット は1個の整数である．次元が高くなると整数のリストになる．
  • 状態とセルの値が，それぞれ1から までと0から までの範囲の整数であるとされる場合，rule として次の形を与えることができる．
n数 n の状態が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,...}}有限テープ，循環を仮定
例題すべて閉じる
例   (4)
4つの0からなるテープで始まる，2状態，2色のマシン2506：
無限の空テープの2状態，2色のマシン2506：
テープの連続する形状をプロットする：
状態の情報をテープの表現に「注入」する：
頭部の位置を赤い正方形で示す：
一組の変換規則で返されたマシン：
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]=
スコープ   (8)
3状態2色のマシン2139050：
ジャンプのオフセットが-との，3状態2色のマシン2139050：
範囲が2の，2状態2色のマシン81756：
頭部を初期テープの位置5に置く：
テープには任意の式が入れられる：
二次元チューリングマシン：
明示的な変化で指定された二次元チューリングマシン：
アプリケーション   (11)
2状態2色マシンの連続する進化を示す：
連続する初期条件からのマシンの頭部の軌跡：
二次元マシンでトレースされた進路：
多くのステップを経た二次元マシンのテープを平均する：
連続する初期条件からの連続する状態列：
連続する初期条件の一連の右または左の動き：
片側テープ上で停止する：
片側テープ上で関数を計算する：
頭部が新たなセルに達したステップだけを示す：
頭部が初期位置に戻ったステップだけを示す：
ランダムな初期テープによる即席のネットワーク：
バージョン 6 の新機能
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
フォーマット:   HTML  |  CDF