TuringMachine

TuringMachine[rule,init,t]
产生一个列表,表示按指定规则运行的图灵机从初始条件 init 开始,演化 t 步的过程.

TuringMachine[rule,init]
给出将初始条件 init 向前演化一步所得的结果.

TuringMachine[rule]
TuringMachine 的运算符形式,相当于向前演化一步.

更多信息更多信息

  • 对于一维图灵机 (Turing machine),TuringMachine 演化的每一步由 {{s,x,dx},{a1,a2,}} 的形式给出,当读写头处于状态 s 时,带中的格子具有值 ai,读写头的位置在相对于 aix 处,并相对于它的初始位置已经移动了 dx.
  • 如果图灵机的初始条件中省略了 dx,则会将其视为 0.
  • 对一个 d 维图灵机,带被指定为一个 d 维的数组,并且位置 x 和相对位置 dx 是长度为 d 的列表.
  • 一个图灵机的规则设定可以通过形式为 {si,ai}->{spi,api,offi} 的列表给出,其中的元素为:
  • si读写头的状态
    ai读写头下面格子的值
    spi读写头的新状态
    api读写头下面格子的新值
    offi读写头的偏移
  • 状态和格子的值可以是整数、模式,或其他表达式. 单个格子的值不能是列表.
  • 在一维情况下,每个位移 offi 是一个单一整数;在多维情况下,它是一个整数列表.
  • 当状态和格子的值分别设置为1 到 s 及0到 k-1 范围内的整数时,rule 的替代形式如下所示:
  • n2 态 2 色带有数字 n 的机器
    {n,s}s 状态,2 色带有数字 n 的机器
    {n,s,k}s 状态,k 色带有数字 n 的机器
    {n,s,k,r}允许位移 offi 在范围 -r+r(不包括 0)
    {n,s,k,{r1,r2,,rd}}d 维机器,带有 +/-r_(1)+/-r_(2), 的偏移
    {n,s,k,{{off1},{off2},}}允许指定位移的机器
    rule带有明确给定规则的机器
  • 可能的图灵机规则的数量为:
  • 2 态 2 色机器4096
    sk 色机器(2 s k)^(s k)
    sk 色范围 r 的机器(2 r s k)^(s k)
    二维 sk 色机器(4 s k)^(s k)
  • 如果机器本身的格局中没有设置任何规则,则它的格局不会发生改变.
  • 起始条件 init 的典型形式为:
  • {s,{{},0}}读写头处于状态 s,在一个全部为 0 的一维带上
    {s,{{a1,a2,},0}}在一个无限带上的限制在 ai 的值的区域
    {{s,x},{{a1,a2,},0}}开始时读写头处于位置 x 的有限区域
    {{s,},{{a1,},{b1,}}}bi 的重复背景
    {{s,},{a1,a2,}}假定循环的有限带
  • TuringMachine[rule,init,t] 生成一个长度为 t+1 的演化列表.
  • TuringMachine[rule][init] 等价于 TuringMachine[rule,init].

范例范例打开所有单元关闭所有单元

基本范例  (4)基本范例  (4)

2 态 2 色机器 2506,开始于由四个 0 组成的带:

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)