Wolfram NKS下的进程代数：形式规范与抽象水平

理论计算机科学电子笔记162（2006）101-105www.elsevier.com/locate/entcsWolfram NKS下的进程代数Tommaso Bolognesi1ISTI-信息科学技术研究所Faedo意大利比萨摘要进程代数定义背后的强大智力投资以及它们在形式规范中可以达到的高度抽象水平，仍然与它们对软件工程实践的渗透程度形成对比，而且与这些模型发挥一定作用的基础科学其他领域的相对有限数量形成对比。Wolfram的“新科学”（NKS）是进程代数可能会引起人们注意的一个新兴领域。在这篇简短的笔记中，我们开始讨论将进程代数置于这种新的视角下的可能动机和初步步骤，并通过NKS风格的实验探索其多功能性。关键词：进程代数，初等元胞自动机，涌现特征，Wolfram序列，伪随机数1无要求的程序：行为类当编写一段面向对象的代码或通过某种过程代数语言指定复杂反应系统的行为时，工程师需要编程或描述与某些预定义功能相匹配的行为，如某些客户要求所表达的。在[1]中，这种观点在某种程度上是颠倒的：人们不再担心实现的功能，而是关注计算本身的内部“形状”。当从人类工程活动中产生的有限的需求库中解放出来时，给定的形式主义是如何表现的？这项研究的关键假设是，我们在自然界中观察到的复杂性本质上是计算性的、离散的，而且可能是确定性的，就像细胞自动机的进化一样。1电子邮件：t. isti.cnr.it1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.106102T. Bolognesi/Electronic Notes in Theoretical Computer Science 162（2006）101在[1]中，几个正式的模型是在这种光下检查。对每一种行为模式都进行了解释性或统计性的调查，目的是对出现的各种行为模式进行可视化和分类。最广泛探索的模型是元胞自动机。一维、双色、最近邻元胞自动机或基本元胞自动机（ECA）是一个无限的黑白细胞阵列，它们根据一个简单的规则以离散的步骤并行（“同步性”）进化。该规则为单元分配新颜色，而不考虑其在阵列中的位置（“均匀性”），仅取决于单元本身及其左右邻居的当前颜色（“局部性”）。 ECA从0开始编号第255章简单的推理当从黑白细胞的随机行开始时，不同的ECA产生不同的视觉模式，Wolfram将其分为四类（[1]，第103页）。231）：在第一类中，行为非常简单，几乎所有的初始条件都导致完全相同的最终状态。在第二类中，有许多不同的可能的最终状态，但它们都只由一组简单的结构组成，这些结构要么永远保持不变，要么每隔几步重复一次。在第3类中，行为更加复杂，在许多方面似乎是随机的[...]第四类是有序和随机的混合：局部结构产生，它们本身相当简单，但这些结构以非常复杂的方式四处移动并相互作用。最 有 趣 的 ECA 是 110 号 ， 原 因 很 简 单 ， 有 首 先 ， 它 的 演 变 （ 见http://www.wolframscience.com/nksonline/page-229）是详细说明：粒子状局域结构在自发建立的周期性背景上以不同的速度运动，并以复杂的方式相互作用，同时保持它们各自的形状，或产生新的粒子，或相互湮灭。第二，自动机是一个通用的计算设备（作为一个副产品，它产生了已知最小的通用图灵机）。2.在普遍性当考虑ECA 110的计算通用性时，各种反应是可能的。例如，一个理论计算机科学家可能对普适性结果本身感到满意，一个工程师可能会尝试对新的通用计算机进行编程，以提取有用的功能，而一个自然科学家参与，比如说，粒子物理学，可能会开始怀疑这些新兴的图形特征是否与我们在自然界中观察到的复杂性有关。NKS式的调查探索了普遍性门槛附近的土地，其科学态度与昆虫学家的态度相差不远一个典型的NKS风格的实验涉及识别计算模型（例如寄存器机器），一些用于测量模型实例复杂性的参数（例如，所有具有五个指令的机器），以及一些方便的可观察变量（例如，仅示出机器寄存器的局部最大值/最小值的图）。然后，探索日益复杂的子模型，以寻找四种行为类别的独特特征的逐步出现为T. Bolognesi/Electronic Notes in Theoretical Computer Science 162（2006）101103关于我们联系我们anaanaana例如，在双寄存器机器（见[1]，第3章）中，仅考虑8个指令，对应于11，019，960，576种可能的情况，似乎随机行为的一些痕迹开始出现（在126个实例中）。3一些初步问题和步骤进程代数有资格进行NKS风格的有意义的实验吗？在NKS的“简单程序世界”中，他们的位置在哪里？哪些变量最能支持对日益复杂的行为的观察第一个印象是，即使在最简单的形式中，进程代数也可能已经太复杂了。虽然已经花费了大量的精力来最小化非确定性和并发性的独立运算符的集合，但在NKS设置中，这些概念可能会变得过于复杂，并且对于我们在自然界中观察到的复杂性的最终解释来说是不必要的。虽然[ 1 ]中研究的尽管如此，我们还是尝试了一些初步的、非常规的过程代数行为观察（用基本LOTOS编写），以寻找快速停滞、周期性、嵌套/分形行为或确定性随机性的痕迹。我们观察到了哪个变量？为了检测Wolfram类的显著特征的出现，可以抽象出状态的许多细节。相当彻底，我们认为在过程代数项作为纯粹的数字生成器：一个行为只是一个给定的行动，说是一个，在连续的深度水平的SOS衍生标记树的发生计数。首先，我们固定了动作（a和b）和过程符号（P和Q）的数量，只考虑了不作为、过程实例、动作前缀、选择、完全并行的运算符。一个规范是P和Q的一对过程定义，以在累积句法深度达到3的情况下观察到的唯一行为是序列0，0，.，1，1，.和1，0，0，... . 对于深度4，唯一的新颖性是周期序列1，0，1，0，.的出现。和0，1，0，1，.和以2为底的几何级数对所有22，192，128个规格的详尽探索，累积深度为5或更广泛的病例。例如，当深度2和3与这两个过程相关联时，我们总共有32，256个规范，产生76个不同的序列。这些包括以2、3和4为基的几何级数，以及基于递归的序列：（一）（二）（三）an=an−1+an−2an=2an−1+an−2=2个n−1（四）（五）=2个n−1=2个n−1+an−1+an−2104T. Bolognesi/Electronic Notes in Theoretical Computer Science 162（2006）101关于我们关于我们⎨----其中通过改变初始值、通过取子集和通过应用比例因子来获得变量。注意，（1）是无处不在的斐波那契序列。递归（2）在初始值为1，3和1，2的情况下都出现，产生序列1，3，7，17，41，99. 1，2，5，12，29，70，... .有趣的是，它们分别对应于连分数的分子和分母，到2002年。通过观察，在这个简单的设置中，加法和乘法的算术运算符有效地在幕后起作用，分别对应于选择和并行合成的运算符，人们可以开始设计一个从过程代数规范直接导出递归的模式。但是，一旦更深的术语和进一步的行为操作符，被认为？这个模式是否总是为我们提供一个找到序列中第n个元素的计算捷径？这让我们回到了NKS的一个中心主题，即计算不可约化。ECA 30演变过程中的中心列是伪随机数发生器的一个众所周知的例子。这个序列中第n位的值只能通过计算它之前的所有ECA状态来获得：没有找到过计算捷径。我们能从进程代数项中提取具有相似属性的数字序列吗？如果是这样的话，这些问题有多复杂？的[1]中提出的类似随机行为的最简单示例是数字序列：an+1 =an<$3/2，如果an是偶数;如果一个n是奇数，则<$（an+1）<$3/ 2当0=1时，序列为1， 3， 6， 9， 15， 24， 36，54。根据规则30的umn，该序列的奇偶校验1， 1， 0， 1， 1， 0， 0，0 表现出随机性。这些特征确实也是在前面提到的8指令寄存器机器中检测到的那些特征。我们基于上述行动计数对该特定数字序列的搜索尚未成功。然而，人们可能会想，选择一个不同的可观测过程代数项演化是否会有导致了不同的结果。 通过采取直接的方法，一个显式模型，因此有点偏离NKS风格，我们得到了以下规格。System：=hide{a，b}in（P[Φ]|{a，b，d}|X）P：= c; d;停止购买力平价：= P| {d}|P| {d}|PX：= hide{c，d}in（（a; RW））|{c，d，b}|（b; X [Φ]））RW：=a;（a;（RW| {d}|PPP）[] b; PPP）[] b; PPPΦ ={a→c，b→d，c→a，d→b，τ→τ}我们仍然使用纯进程代数，但我们需要一个更灵活的并行操作符，具有选择性同步，隐藏操作符和带有动作重新标记的进程实例化。作为一个新的可观察量，我们选择了相同标记的转换的运行长度。从左到右，我们的规范T. Bolognesi/Electronic Notes in Theoretical Computer Science 162（2006）101105出现为一系列不断增长的组合爆炸（图1），其动作依次标记为a和c，b和d作为分隔符，其直径为{1，3，6，9，15，24，36，54. }，也就是WolframFig. 1. 长度为{1，3，6，9，. }在过程代数设置中，是否有可能明确区分第3类和第4类行为？NKS中的一个未决问题是，是否确实可以在第3类中实现计算普适性，例如通过ECA30.在这方面，寻找伪随机扰动的出现在各种正式的系统，包括进程代数，似乎是一个有吸引力的目标。引用[1]斯蒂芬·沃尔夫勒姆一种新的科学。Wolfram Media，Inc. 2002年。