Wolfram言語＆システムドキュメントセンター

TuringMachine

TuringMachine[rule,init,t]

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

TuringMachine[rule,init]

init を1ステップ進化させた結果を与える．

TuringMachine[rule]

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

詳細

一次元のチューリングマシンの場合，TuringMachineで生成された進化の各ステップは{{s,x,dx},{a₁,a₂,…}}の形で与えられる．ここで，頭部の状態は s であり，テープ上のセルは値 a_iを持ち，頭部は a_iと相対的な位置 x にあり，初期位置と比べて dx 動いている．
dx がチューリングマシンの初期条件から省略された場合，dx は0とみなされる．
d 次元のチューリングマシンでは，テープは d 次元の配列で指定され，位置 x と相対的位置 dx は長さ d のリストになる．
チューリングマシンのルールは{s_i,a_i}->{sp_i,ap_i,off_i}の形の置換のリストで与えられる．その要素は次のようになる．

	s_i	頭部の状態
	a_i	頭部の下のセルの値
	sp_i	頭部の新しい状態
	ap_i	頭部の下のセルの新しい値
	off_i	頭部が動くオフセット

状態とセルの値は整数，パターン，任意の式のいずれでもよい．個々のセルの値はリストにはできない．
一次元では，各オフセット off_iは1個の整数である．次元が高くなると整数のリストになる．
状態とセルの値が，それぞれ1からまでと0からまでの範囲の整数であるとされる場合，rule として次の形を与えることができる．

	n	数 n の状態が2つで色も2色のマシン
	{n,s}	数 n の状態が s 個で色が2色のマシン
	{n,s,k}	数 n の状態が s 個で色が k 色のマシン
	{n,s,k,r}	からの範囲（0を除く）で off_iを許容する
	{n,s,k,{r₁,r₂,…,r_d}}	オフセット, , …の次元マシン
	{n,s,k,{{off₁},{off₂},…}}	指定された明示的オフセットを許容するマシン
	{rule,s,k}	明示的なルールを与えられたマシン
	rule	明示的なルールを与えられたマシン（s と k は推測される）

可能なチューリングマシンルールの数は次の通りである．

	2状態2色のマシン	4096
	s 状態 k 色のマシン	(2 s k)^(s k)
	s 状態 k 色で範囲 r のマシン	(2 r s k)^(s k)
	二次元で s 状態 k 色のマシン	(8 s k)^(s k)

マシンがそれ自身が置かれている構造についてのルールを持たない場合，その構造は変化しない．
TuringMachineは，与えられた構成に対してルールが複数の指定を持っている場合はリストの先頭の物を使う．
{rule,s,k}の形を使って，指定された構成に対してルールに必ずしも1つの例しかない訳ではない，多方向，非決定性，あるいはその他のチューリングマシンが指定できる．
典型的な初期条件 init の形は次の通りである．

	{s,{{},0}}	頭部の状態 s，0で埋められた一次元テープ上
	{s,{{a₁,a₂,…},0}}	無限テープ上の値 a_iで区切られた範囲
	{{s,x},{{a₁,a₂,…},0}}	頭部が最初は位置 xにある有限範囲
	{{s,…},{{a₁,…},{b₁,…}}}	値 b_iの反復する背景
	{{s,…},{a₁,a₂,…}}	有限テープ，循環を仮定

TuringMachine[rule,init,t]は，長さの進化リストを生成する．
TuringMachine[rule][init]はTuringMachine[rule,init]に等しい．

例題

すべて開くすべて閉じる

例 (5)

初期テープが4つの0からなり3ステップ進化する，2状態，2色のマシン2506：

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 3]

無限の0のテープの4ステップ進化する，2状態，2色のマシン2506：

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 4]

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

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{}, 0}}, 30]]

チューリングマシンのルールアイコンを表示する：

Wolfram Language code: RulePlot[TuringMachine[2506]]

ヘッドの状態も含め，進化をプロットする：

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 20]

明示的な遷移で指定されたチューリングマシンのルールアイコンを示す：

Wolfram Language code: RulePlot[TuringMachine[{{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}}]]

頭部の状態も含めて進化をプロットする：

Wolfram Language code:

RulePlot[TuringMachine[{{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}}], {1, {{}, 0}}, 20]

パターンに基づく遷移規則で指定されたチューリングマシン：

Wolfram Language code:

TuringMachine[{
	{state_, color_ ? EvenQ} :> {state, color / 2, -1}, {state_, color_ ? OddQ} :> {state, 3color + 1, 1}}, 
	{1, {1, 2, 3, 4, 5}}, 5]

スコープ (17)

一次元ルール (6)

2状態1色のマシン2506：

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 4]//Grid

進化をプロットする：

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{}, 0}}, 20]]

ヘッドの状態も含め，進化をプロットする：

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 20]

3状態2色のマシン2139050：

Wolfram Language code: RulePlot[TuringMachine[{2139050, 3}], {1, {{}, 0}}, 30]

ルールアイコンを生成する：

Wolfram Language code: RulePlot[TuringMachine[{2139050, 3}]]

範囲が2で2状態2色のマシン16220：

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[{16220, 2, 2, 2}, {1, {{}, 0}}, 50]]

ジャンプのオフセットがと2の，3状態2色のマシン2139050：

Wolfram Language code: evolution = TuringMachine[{2139050, 3, 2, {{-1}, {2}}}, {1, {{}, 0}}, 45];

Wolfram Language code: ArrayPlot[Last /@ evolution]

明示的な遷移規則を与える：

Wolfram Language code:

evolution = TuringMachine[
	{{state_, color_} :> {color * state, color / state, 1}}, 
	{1, {2, 3, 4, 5}}, 4];

Wolfram Language code: evolution//Grid

同じ遷移規則に対して状態数 s と色数 k の値を明示的に指定する：

Wolfram Language code: rules = {{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}};

Wolfram Language code: RulePlot[TuringMachine[{rules, 2, 2}]]

Wolfram Language code: RulePlot[TuringMachine[{rules, 3, 3}]]

初期条件 (9)

ヘッドの指定 (4)

ヘッドの状態が1から始まる，2状態2色のマシン2506：

Wolfram Language code: TuringMachine[2506, {{1}, {{}, 0}}, 4]//Grid

進化：

Wolfram Language code: RulePlot[TuringMachine[2506], {{1}, {{}, 0}}, 20, PlotLegends -> "Icon"]

ヘッドの状態が2から始まる，2状態2色のマシン2506：

Wolfram Language code: TuringMachine[2506, {{2}, {{}, 0}}, 4]//Grid

進化：

Wolfram Language code: RulePlot[TuringMachine[2506], {{2}, {{}, 0}}, 10, PlotLegends -> "Icon"]

初期テープでヘッドを位置3に置く：

Wolfram Language code: RulePlot[TuringMachine[2506], {{1, 3}, {0, 0, 0, 0, 1, 0, 0}}, 10, PlotLegends -> "Icon"]

初期テープでヘッドを位置5に置く：

Wolfram Language code: RulePlot[TuringMachine[2506], {{1, 5}, {0, 0, 0, 0, 1, 0, 0}}, 10, PlotLegends -> "Icon"]

テープの指定 (5)

循環を仮定して，4個の0を持つ有限テープで始める：

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 5]//Grid

最も左のセルの左近傍は最も右のセルであり，逆もまた真である：

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {0, 0, 0, 0}}, 10]

0の無限テープで始める：

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 18]

無限に0がある背景上の1のテープで始める：

Wolfram Language code: RulePlot[TuringMachine[{956440, 3}], {1, {{1}, 0}}, 20]

0の背景上のブロック211からなるテープで始める：

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{2, 1, 1}, 0}}, 10]

繰り返される02ブロックの背景上のブロック211で始める：

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{2, 1, 1}, {0, 2}}}, 10]

多次元ルール (2)

2Dの2状態2色のチューリングマシン977401：

Wolfram Language code: rule = {977401, 2, 2, {1, 1}};

Wolfram Language code: TuringMachine[rule, {1, {{{}}, 0}}, 4]

Wolfram Language code:

ic = {1, Table[0, {10}, {10}]};
steps = 30;

Wolfram Language code: Graphics3D[Cuboid /@ Position[Last /@ TuringMachine[rule, ic, steps], 1]]

明示的な遷移で指定された二次元チューリングマシン：

Wolfram Language code:

rules = {
	{1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, 
	{2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, 
	{3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, 
	{4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}};

Wolfram Language code: ArrayPlot[TuringMachine[rules, {1, {{{}}, 0}}, 8000][[-1, -1]]]

アプリケーション (12)

無限の0のテープからのWolframの単純なユニバーサルチューリングマシンの進化：

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{}, 0}}, 80]

明示的な規則を使った別の形式：

Wolfram Language code:

rules = {{1, 2} -> {1, 1, -1}, {1, 1} -> {1, 2, -1}, {1, 0} -> {2, 1, 1}, {2, 2} -> {1, 0, 1}, {2, 1} -> {2, 2, 1}, {2, 0} -> {1, 2, -1}};

Wolfram Language code: RulePlot[TuringMachine[rules], {1, {{}, 0}}, 80]

2状態2色マシンの連続する進化を示す：

Wolfram Language code: Table[RulePlot[TuringMachine[n], {1, {{}, 0}}, 40, ImageSize -> {Automatic, 100}], {n, 2500, 2510}]

連続する初期条件からのマシンのヘッドの軌跡：

Wolfram Language code: ic[n_] := {{1, -2, 0}, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ListLinePlot[Table[#[[1, 3]]& /@ TuringMachine[1507, ic[i], 180], {i, 1, 40}]]

二次元マシンのヘッドでトレースされた進路：

Wolfram Language code:

rules = {
	{1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, 
	{2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, 
	{3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, 
	{4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}};

Wolfram Language code: evolution = TuringMachine[rules, {1, {{{}}, 0}}, 200];

Wolfram Language code:

arrow = Arrow[#[[1, 3]]& /@ evolution];
initpoint = Point[First[evolution][[1, 3]]];

Wolfram Language code: Graphics[{Arrowheads[.1], arrow, PointSize[Large], Gray, initpoint}]

多くのステップを経る二次元マシンのテープを平均する：

Wolfram Language code:

rules = {27726, 2, 2, {1, 1}};
ic = {1, Table[0, {50}, {50}]};

Wolfram Language code: ArrayPlot[Total[Last /@ TuringMachine[rules, ic, 5000]]]

連続する初期条件からの連続する状態列：

Wolfram Language code: ic[n_] := {1, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ArrayPlot[Table[#[[1, 1]]& /@ TuringMachine[1507, ic[i], 100], {i, 1, 100}] - 1]

連続する初期条件の一連の右または左への動き：

Wolfram Language code: ic[n_] := {1, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ArrayPlot[Table[Differences[#[[1, 3]]& /@ TuringMachine[1507, ic[i], 100]], {i, 1, 100}] /. -1 -> 0]

片側テープ上で停止する：

Wolfram Language code:

TuringPlot[evolution_, opts___] := ArrayPlot[MapAt[Blend[{If[# === Orange, #, GrayLevel[#]], Red}]&, #[[2]], #[[1, 2]]]& /@ (evolution /. Null -> Orange), opts]

Wolfram Language code:

Row[Table[TuringPlot[TuringMachine[1507, {{1, -2, 0}, Append[IntegerDigits[i, 2, 10], Null]}, 15], Mesh -> True, ImageSize -> Tiny], {i, 10}], Spacer[10]]

片側テープ上で関数を計算する：

Wolfram Language code:

ListPlot[Table[Last@TuringMachine[1507, {{1, -2, 0}, Append[IntegerDigits[i, 2, 20], Null]}, 50] /. {{{_, z_, _}, y_} /; y[[z]] === Null :> FromDigits[Most[y], 2], _ -> Null}, {i, 1, 1000}], Filling -> Axis]

ヘッドが新たなセルに達するステップだけを示す：

Wolfram Language code:

Module[{new}, new[x_] := (new[x] = False;True);
	RulePlot[TuringMachine[{2791284850, 4}], 
	Cases[
	TuringMachine[{2791284850, 4}, {1, {{}, 0}}, 200], {{_, _, _ ? new}, _}], 
	Mesh -> True]
	]

ヘッドが初期位置に戻るステップだけを示す：

Wolfram Language code: RulePlot[TuringMachine[1413], Select[TuringMachine[1413, {1, RandomInteger[1, 100]}, 6000], #[[1, 2]] === 1&]]

ランダムな初期テープによる因果ネットワーク：

Wolfram Language code:

GraphPlot[With[{rules = MapIndexed[{First[#2], #[[1, 2]], #[[2, #[[1, 2]]]]}&, TuringMachine[1507, {1, RandomInteger[1, 30]}, 200]]}, Join[Rule@@@Partition[rules, 2, 1], Flatten[Rule@@@Partition[#, 2, 1]& /@ Last@Reap[Sow[#, #[[2]]]& /@ rules], 1]]]]

特性と関係 (5)

初期テープが4つの0で1ステップ進化する，2状態，2色のマシン2506：

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}]

同様に，初期状態の演算子形を使う：

Wolfram Language code: TuringMachine[2506][{1, {0, 0, 0, 0}}]

結果はこのリストの2番目の要素と一致する：

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 1]

{n,s,k,…}の形式の規則のときは，ヘッドの状態とセルの値は，それぞれ1から s と0から k-1の整数でよい：

Wolfram Language code:

rule = {596440, 2, 4};
inithstate = 2;
initcvalues = {{}, {2, 1, 3}};

Wolfram Language code: TuringMachine[rule, {inithstate, initcvalues}, 5]//Grid

{n,s,k,…}の形式の規則のときは，0から k-1までの範囲外の値を持つセルにヘッドが到達するとマシンの進化が停止する：

Wolfram Language code:

rule = {596440, 2, 4};
inithstate = 2;
initcvalues = {{}, {2, 1, 8}};

Wolfram Language code: TuringMachine[rule, {inithstate, initcvalues}, 5]//Grid

進化が停止する別のチューリングマシン：

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{0, 0, 0, 0, 0, x, 0}, 0}}, 40]]

明示的な規則の集合を使って停止する状態を定義する：

Wolfram Language code:

rules = {
	{1, 0} -> {1, 1, 1}, {1, 1} -> {2, 1, -1}, 
	{2, 0} -> {1, 1, 1}, {2, 1} -> {2, 1, 0}};

Wolfram Language code: RulePlot[TuringMachine[rules]]

進化をプロットする：

Wolfram Language code: RulePlot[TuringMachine[rules], {1, {{1, 0}, 0}}, 8]

チューリングマシンの進化を生成する：

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 6]

状態情報をテープの表現に「注入」する：

Wolfram Language code: Function[u, MapAt[{u[[1, 1]], #}&, u[[2]], u[[1, 2]]]] /@ TuringMachine[2506, {1, {{}, 0}}, 6]

ヘッドの位置を赤い四角で示す：

Wolfram Language code: ArrayPlot[Function[u, MapAt[Red&, u[[2]], u[[1, 2]]]] /@ TuringMachine[2506, {1, {{}, 0}}, 50]]

RulePlotを使って完全な進化の図を生成する：

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 50]

Top

その他のラーニングリソース

テクニカルサポート

データサイエンス，金融，ビジネス

工学

科学とテクノロジー

教育のためのテクノロジー

教育イニシアチブ

使い始める

Grow Your Skills

Wolframと繋がる

大人用の教育プログラム

若者のための教育プログラム

読む

TuringMachine

詳細

例題

例 (5)

スコープ (17)

一次元ルール (6)

初期条件 (9)

ヘッドの指定 (4)

テープの指定 (5)

多次元ルール (2)

アプリケーション (12)

特性と関係 (5)

テキスト

CMS

APA

BibTeX

BibLaTeX

TuringMachine

詳細

例題

例 (5)

スコープ (17)

一次元ルール (6)

初期条件 (9)

ヘッドの指定 (4)

テープの指定 (5)

多次元ルール (2)

アプリケーション (12)

特性と関係 (5)

関連項目

関連するガイド

関連リンク

履歴

テキスト

CMS

APA

BibTeX

BibLaTeX