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